Bob wants to date with Alice, but they are in different
cities. There are n cities and m roads. Each road is bidirectional. Going through
each road will cost some time. Bob wants to meet Alice at one of the cities as soon as possible. Could you help him to find the minimum time cost?
All cities are labeled from 1 to n.
Note: There may be multiple roads between
some cities. Alice can also move.
The first line will be an integer T. (1
<= T <= 50) T is the number of test cases.
For each test case, the first line will be
two integers n and m. (1 <= n <= 6000, 1 <= m <= 100000)
Then there will be m lines. Each line will
contain three integers u, v, w, meaning there is a road between city u and city
v with time cost w. (1 <= u, v
<= n, u!=v, 1 <= w <= 105)
The last line of each test case is two
integer s and t. (1 <= s, t <= n), meaning the location of Bob and Alice.
The input guarantees Bob can always meet
For each test case, print the minimum time cost.
For the first sample, Bob goes to city 2, and
waits 1 unit of time. Alice goes to city 2 directly, they will meet each other at
4 unit of time.