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 <= 10⁵)

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 Alice.

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.