Critical 3-Path

A PERT (Program Evaluation and Review Technique) chart is a graphical tool used in project management to model the tasks needed to complete a project. It is a directed acyclic graph: each edge represents a task, and the weight of an edge is the time required to perform that task. If an edge $(u, v)$ enters vertex $v$ and an edge $(v, w)$ leaves $v$, then task $(u, v)$ must be finished before task $(v, w)$ can start, so a path through the chart is a sequence of tasks that must be carried out in a fixed order. The chart contains no cycle.

A critical path is a longest path in the chart. Its weight is a lower bound on the total time needed to finish every task.

Given six distinct vertices $s_1, s_2, s_3, t_1, t_2, t_3$, a 3-path is defined as follows:

1. It consists of three paths $P_i$, where each $P_i$ goes from $s_i$ to $t_i$ for $i = 1, 2, 3$.
2. The paths $P_1, P_2, P_3$ are vertex-disjoint: no vertex belongs to more than one of them.

The length of a 3-path is the sum of the lengths (total edge weight) of $P_1$, $P_2$, and $P_3$. A critical 3-path is a 3-path of maximum length over all 3-paths.

For example, in the graph of the first sample below with $s = (3, 4, 5)$ and $t = (15, 16, 17)$, one critical 3-path is:

• $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$

and its length is $128$.

Given a PERT chart and the six vertices, write a program that outputs the length of the critical 3-path.

The first line contains the number of test cases $T$. Each test case begins with a line containing two integers $n$ and $m$ ($6 \le n \le 100$, $n - 1 \le m \le n(n-1)/2$), where $n$ is the number of vertices and $m$ is the number of edges. Vertices are numbered from $1$ to $n$. The next line contains six distinct integers $s_1, s_2, s_3, t_1, t_2, t_3$. Each of the following $m$ lines contains three integers $u$, $v$, and $W$ ($1 \le W \le 100{,}000$), describing a directed edge from $u$ to $v$ with weight $W$. You may assume that $u < v$ for every edge.

For each test case, print a single line containing the length of the critical 3-path formed by $P_1$ (from $s_1$ to $t_1$), $P_2$ (from $s_2$ to $t_2$), and $P_3$ (from $s_3$ to $t_3$). If no such 3-path exists, print $0$.