임계 3-경로

PERT(Program Evaluation and Review Technique) 차트는 프로젝트 관리에서 프로젝트를 완료하는 데 필요한 작업들을 표현하는 그래프 도구입니다. 이 차트는 방향 비순환 그래프이며, 각 간선은 하나의 작업을, 간선의 가중치는 그 작업을 수행하는 데 걸리는 시간을 나타냅니다. 간선 $(u, v)$가 정점 $v$로 들어오고 간선 $(v, w)$가 $v$에서 나간다면, 작업 $(u, v)$를 작업 $(v, w)$보다 먼저 끝내야 합니다. 따라서 차트의 한 경로는 정해진 순서대로 수행해야 하는 작업들의 나열입니다. 이 차트에는 사이클이 없습니다.

임계 경로(critical path)는 차트에서 가장 긴 경로이며, 그 가중치는 모든 작업을 끝내는 데 필요한 전체 시간의 하한입니다.

서로 다른 여섯 개의 정점 $s_1, s_2, s_3, t_1, t_2, t_3$에 대해 3-경로를 다음과 같이 정의합니다.

1. 3-경로는 세 개의 경로 $P_i$로 이루어지며, 각 $P_i$는 $s_i$에서 $t_i$로 가는 경로입니다($i = 1, 2, 3$).
2. 세 경로 $P_1, P_2, P_3$는 정점을 공유하지 않습니다. 즉 어떤 정점도 둘 이상의 경로에 속하지 않습니다.

3-경로의 길이는 $P_1$, $P_2$, $P_3$의 길이(간선 가중치의 합)를 모두 더한 값입니다. 임계 3-경로는 가능한 모든 3-경로 중에서 길이가 최대인 3-경로입니다.

예를 들어 아래 첫 번째 예제의 그래프에서 $s = (3, 4, 5)$, $t = (15, 16, 17)$이라 하면, 하나의 임계 3-경로는 다음과 같습니다.

• $P_1$: $3 \to 6 \to 11 \to 15$
• $P_2$: $4 \to 7 \to 9 \to 12 \to 16$
• $P_3$: $5 \to 8 \to 13 \to 17$

이때 길이는 $128$입니다.

PERT 차트와 여섯 개의 정점이 주어질 때, 임계 3-경로의 길이를 구하는 프로그램을 작성하세요.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어지며($6 \le n \le 100$, $n - 1 \le m \le n(n-1)/2$), $n$은 정점의 수, $m$은 간선의 수입니다. 정점은 $1$부터 $n$까지 번호가 매겨집니다. 다음 줄에는 서로 다른 여섯 정수 $s_1, s_2, s_3, t_1, t_2, t_3$가 주어집니다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $W$가 주어지며($1 \le W \le 100{,}000$), 이는 정점 $u$에서 $v$로 가는 가중치 $W$의 방향 간선을 뜻합니다. 모든 간선에 대해 $u < v$라고 가정해도 됩니다.

각 테스트 케이스마다 한 줄에, $P_1$($s_1$에서 $t_1$), $P_2$($s_2$에서 $t_2$), $P_3$($s_3$에서 $t_3$)으로 이루어진 임계 3-경로의 길이를 출력합니다. 그러한 3-경로가 존재하지 않으면 $0$을 출력합니다.