Longest Common Path

Time limit1sMemory limit256 MB

Summary

Two friends each walk a shortest route from school to their own home, and the goal is to maximize the shared consecutive stretch of both routes.

Level: Medium7 of 10
Topics: Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

Per and Pal are friends and spend a lot of time together. Both are impatient, so whenever they go somewhere they take a fastest route.

School is over and they have to go home. Each one wants to get home as early as possible, and they also want to walk together for as long as they can.

The neighbourhood is a graph whose nodes are intersections and whose edges are roads. Every road is bidirectional and takes the same time in either direction. The school and the two homes sit at intersections, and the three positions are different. Some path connects every pair of intersections.

Per and Pal leave school at the same moment, and each one picks a shortest route to his own home. Choose the two routes so that the total travel time of a run of consecutive roads contained in both routes is as large as possible. Write a program that computes that time.

Input

The first line contains one integer $T$ , the number of test cases.

The first line of each test case contains two integers $N$ and $M$ , the number of intersections and the number of bidirectional roads. The second line contains three integers $S$ , $P$ and $Q$ , the intersections of the school, Per's home and Pal's home. Each of the next $M$ lines contains three integers $a_i$ , $b_i$ and $c_i$ , meaning that a bidirectional road joins intersections $a_i$ and $b_i$ and takes $c_i$ minutes to traverse. Intersections are numbered from $0$ to $N-1$ .

$0 < T \le 100$
$3 \le N \le 2000$
$N - 1 \le M \le \min(N(N-1)/2, 10000)$
$0 \le a_i < b_i < N$
$0 < c_i \le 1000$
$0 \le S, P, Q < N$ , and $S$ , $P$ , $Q$ are pairwise distinct
At most one road joins any pair of intersections, and every intersection is reachable from every other one

Output

For each test case, print on one line the length of the longest stretch Per and Pal can walk together while both still reach their own homes as fast as possible. Print $0$ when no road lies on both routes.

Examples6

Example 1

Input

Expected output

100
0

Example 2
Input
```
1
3 3
0 1 2
0 1 5
0 2 7
1 2 1
```
Expected output
```
5
```
Example 3
Input
```
1
4 4
0 1 2
0 1 1
0 2 1
0 3 1
1 2 5
```
Expected output
```
0
```
Example 4
Input
```
1
5 4
0 4 2
0 1 2
1 2 3
2 3 4
3 4 5
```
Expected output
```
5
```

Example 5

Input

Expected output

Example 6

Input

Expected output