Constructing Roads
Problem Description
Long long ago, There was a country named X, the country has N cities which are numbered from 1 to N.
The king of Country-X wants to construct some roads.
Please note that Country-X is blessed by an angel. He(The angel is a boy? This is no science, but do not care about those details, this angel is so cute, he must be a boy) can use magic to make one road connections directly from two cities’ cost to be half, but the magic can only be used once.
The king wants to know the minimal cost to construct a road between City-A and City-B. Because of there are so many cities and roads, the construction division comes to you, the only programmer he knows, for help.
You should write a program to calculate the minimal cost between City-A and City-B to help him.
Input
For each test case:
The fist line is two integers N and M (2 <= N <= 1000，0 <= M <= 50000).
Each of the following M lines contains three integers U、V and W (1<= U,V<= N, 0 <= W <= 1000) . It shows that if we construct a road between the U-th city and the V-th city , the cost is W.
The next line is two integers A and B (1<= A, B <= N).
Output
Sample Input
2 1 1 2 99 1 2 4 3 1 2 312 2 3 520 3 1 999 3 4
Sample Output
49 No solution