T830135 线路通票（pass）

城市里有 $N$ 个车站，编号为 $1\sim N$，以及 $M$ 条双向线路。第 $i$ 条线路连接车站 $A_i$ 和 $B_i$，每次乘坐这条线路需要支付 $C_i$ 元。任意两个车站之间都可以通过若干条线路到达。 你准备购买一张从车站 $S$ 到车站 $T$ 的线路通票。购买时，必须在原来的票价下，选定一条从 $S$ 到 $T$ 的总票价最小的路线。如果有多条这样的路线，可以任选其中一条。 通票选定后，这条路线上的所有线路都可以免费乘坐，而且两个方向都免费；不在这条路线上的线路仍按原票价收费。不能同时选择多条路线，也不能在之后的行程中更换通票路线。 你还需要从车站 $U$ 前往车站 $V$。你可以自由选择这次行程的路线，可以使用通票中的部分线路，也可以完全不使用通票。 请合理选择通票路线和从 $U$ 到 $V$ 的行程，使这次行程实际支付的总票价尽可能小，并输出这个最小值。不计购买通票本身的费用。

第一行一个整数 $Q$，表示数据组数。 对于每组数据： - 第一行两个整数 $N,M$。 - 第二行两个整数 $S,T$。 - 第三行两个整数 $U,V$。 - 接下来 $M$ 行，第 $i$ 行三个整数 $A_i,B_i,C_i$，描述第 $i$ 条双向线路。

对于每组数据，输出一行一个整数，表示从 $U$ 到 $V$ 最少实际支付的总票价。

从 $1$ 到 $6$ 的原票价最小路线唯一，为 $1\to2\to3\to5\to6$，原票价总和为 $4$ 元，通票覆盖这条路线上的线路。 从 $1$ 到 $4$ 时，可以沿 $1\to2\to3\to5\to4$ 行驶。前三段免费，最后一段 $5\to4$ 支付 $2$ 元，总共支付 $2$ 元。车站 $4$ 不在通票路线中，进入它至少需要乘坐一条收费线路，而与它相连的线路票价最小为 $2$ 元，因此不能更少。 ## 样例 2 见 `考生目录/pass/pass2.in` 与 `考生目录/pass/pass2.ans`。该样例满足测试点 $1\sim3$ 的约束。 ## 样例 3 见 `考生目录/pass/pass3.in` 与 `考生目录/pass/pass3.ans`。该样例满足测试点 $4\sim6$ 的约束。 ## 样例 4 见 `考生目录/pass/pass4.in` 与 `考生目录/pass/pass4.ans`。该样例满足测试点 $7\sim11$ 的约束。 ## 样例 5 见 `考生目录/pass/pass5.in` 与 `考生目录/pass/pass5.ans`。该样例满足测试点 $12\sim20$ 的约束。 ## 样例 6 见 `考生目录/pass/pass6.in` 与 `考生目录/pass/pass6.ans`。该样例满足测试点 $12\sim20$ 的约束。 ## 数据范围 对于所有数据，保证： - $1\le Q\le10$； - 每组数据中，$2\le N\le10^5$，$1\le M\le2\times10^5$； - $1\le S,T,U,V\le N$，$S\ne T$，$U\ne V$，且不同时满足 $S=U$ 和 $T=V$； - $1\le A_i