帮国王省钱

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

国王想在n个城市之间修路,就找星际商人来谈价钱,很多商人都觉得这个国王太抠门就没有来,只有商人甲来了,提出了很便宜的价格,并承诺可以使修的其中一条路的价格成为原价的五折,但只有一条。
国王很高兴,但是还是算不出来怎样才能使城市A到城市B的道路的造价最低。
你能帮助他吗?

Input

输入数据有多组 ,到文件结束。
每一组第一行是n, m;代表有n个城市,所有的城市之间一共有m条路是可以建造的。
1<n<=1000,0<=m<=50000;
接下来有m行,每行有三个数u,v,w代表城市u到城市v之间的路造价为w.0<u,v<=n.0<=w<=1000
接下来有一行,有两个数A,B,代表国王想修从城市A到城市B之间的路。1<= A, B <= N
数据保证图是连通图

Output

对于每一组输入输出一行有一个数,代表最小花费。若除以二有小数需取整。详看样例。

Sample Input

2 1
1 2 99
1 2

Sample Output

49

Hint

 

Source

lin