Constructing Roads

Time Limit: 1000 ms Memory Limit: 65536 KiB

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

    There are multiple test cases.
    For each test case:
    The fist line is two integers N and M (2 <= N <= 10000 <= M <= 50000).
    Each of the following M lines contains three integers UV 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

    For each test case,output one line containing the minimal cost , if there is no route from A to B , the output should contain the string “No solution” (without the quotes).

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

Hint

 We define that the half of 100 is 50 and the half of 99 is 49.

Source

qinchuan