Problem G: Bob with Alice

Problem G: Bob with Alice

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1668  Solved: 304
[Submit][Status][Web Board]

Description

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.

Input

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

Output

For each test case, print the minimum time cost.

Sample Input

2
4 3
1 2 3
3 2 1
2 4 4
1 4
8 7
1 2 1
1 3 7
1 4 6
4 6 2
6 5 4
6 7 3
7 8 5
4 7

Sample Output

4
3

HINT


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.

[Submit][Status]