Longest Common Path

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.

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

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.