함께 걷는 가장 긴 길

페르와 폴은 친구라서 자주 같이 다닌다. 둘 다 성격이 급해서 어디를 가든 항상 가장 빠른 길로만 간다.

수업이 끝나 집에 갈 시간이 됐다. 두 사람은 각자 집에 최대한 일찍 도착하고 싶고, 그러면서 함께 걷는 시간은 최대한 길게 만들고 싶다.

동네는 교차로가 정점이고 도로가 간선인 그래프로 나타낸다. 도로는 양방향이고, 어느 쪽으로 지나든 걸리는 시간이 같다. 학교와 두 사람의 집은 모두 교차로에 있으며, 세 위치는 서로 다르다. 어떤 두 교차로 사이에도 경로가 존재한다.

두 사람은 같은 순간에 학교를 떠나 각자 자기 집으로 가는 최단 경로를 하나씩 고른다. 두 경로를 잘 골라서, 두 경로에 모두 들어 있는 연속된 도로 구간의 총 소요 시간을 최대로 만들어라. 그 시간을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 교차로의 개수 $N$과 양방향 도로의 개수 $M$이 주어진다. 둘째 줄에는 학교, 페르의 집, 폴의 집이 있는 교차로 번호 $S$, $P$, $Q$가 주어진다. 이어지는 $M$개의 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어지고, 이는 교차로 $a_i$와 $b_i$를 잇고 지나는 데 $c_i$분이 걸리는 양방향 도로가 있다는 뜻이다. 교차로 번호는 $0$부터 $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$이고 $S$, $P$, $Q$는 서로 다르다
• 같은 두 교차로를 잇는 도로는 많아야 하나이고, 모든 교차로는 서로 연결되어 있다

각 테스트 케이스마다 두 사람이 각자 집에 가장 빨리 도착하면서 함께 걸을 수 있는 가장 긴 구간의 길이를 한 줄에 출력한다. 두 경로가 공유하는 도로가 하나도 없으면 $0$을 출력한다.