CF1737D.Ela and the Wiring Wizard

Ela needs to send a large package from machine $1$ to machine $n$ through a network of machines. Currently, with the network condition, she complains that the network is too slow and the package can't arrive in time. Luckily, a Wiring Wizard offered her a helping hand.

The network can be represented as an undirected connected graph with $n$ nodes, each node representing a machine. $m$ wires are used to connect them. Wire $i$ is used to connect machines $u_i$ and $v_i$, and has a weight $w_i$. The aforementioned large package, if going through wire $i$, will move from machine $u_i$ to machine $v_i$ (or vice versa) in exactly $w_i$ microseconds. The Wiring Wizard can use his spell an arbitrary number of times. For each spell, he will choose the wire of index $i$, connecting machine $u_i$ and $v_i$, and rewire it following these steps:

• Choose one machine that is connected by this wire. Without loss of generality, let's choose $v_i$.
• Choose a machine that is currently connecting to $v_i$ (including $u_i$), call it $t_i$. Disconnect the wire indexed $i$ from $v_i$, then using it to connect $u_i$ and $t_i$.

The rewiring of wire $i$ will takes $w_i$ microseconds, and the weight of the wire will not change after this operation. After a rewiring, a machine might have some wire connect it with itself. Also, the Wiring Wizard has warned Ela that rewiring might cause temporary disconnections between some machines, but Ela just ignores it anyway. Her mission is to send the large package from machine $1$ to machine $n$ as fast as possible. Note that the Wizard can use his spell on a wire zero, one, or many times. To make sure the network works seamlessly while transferring the large package, once the package starts transferring from machine $1$, the Wiring Wizard cannot use his spell to move wires around anymore.

Ela wonders, with the help of the Wiring Wizard, what is the least amount of time needed to transfer the large package from machine $1$ to $n$.

Ela 需要通过一个机器网络，将一个大型包裹从机器 $1$ 发送至机器 $n$。当前网络状况下，她抱怨网络太慢，包裹无法及时到达。幸运的是，一位“布线巫师”主动提出帮助。

该网络可建模为一个含 $n$ 个节点的无向连通图，每个节点代表一台机器；共有 $m$ 根导线用于连接这些机器。第 $i$ 根导线连接机器 $u_i$ 和 $v_i$，其权重为 $w_i$。若该大型包裹经由第 $i$ 根导线传输，则它将恰好耗时 $w_i$ 微秒，从机器 $u_i$ 移动到机器 $v_i$（或反向移动）。布线巫师可任意多次施放他的魔法。每次施法时，他将选定索引为 $i$ 的导线（连接机器 $u_i$ 和 $v_i$），并按以下步骤重布此导线：

• 选择该导线所连接的其中一台机器；不失一般性，设其为 $v_i$；
• 再选择一台当前与 $v_i$ 相连的机器（包括 $u_i$），记作 $t_i$；断开导线 $i$ 与 $v_i$ 的连接，并用它重新连接 $u_i$ 和 $t_i$。

对导线 $i$ 执行一次重布操作需耗时 $w_i$ 微秒，且该导线的权重 $w_i$ 在操作后保持不变。重布后，某台机器可能通过某根导线与自身相连。此外，布线巫师已警告 Ela：重布操作可能导致某些机器之间出现临时性断连；但 Ela 并不在意这一点。她的目标是尽可能快地将大型包裹从机器 $1$ 传送至机器 $n$。注意：巫师可对任意一根导线施法零次、一次或多次。为确保包裹传输过程中网络运行无缝衔接，一旦包裹开始从机器 $1$ 出发传输，布线巫师便不能再施法移动任何导线。

Ela 想知道，在布线巫师的帮助下，将大型包裹从机器 $1$ 传送到机器 $n$ 所需的最短时间是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line contains $n$ and $m$ ($2 \le n \le 500$, $n - 1 \le m \le 250 000$), the number of nodes and number of wires, respectively.

For the next $m$ lines, $i$-th line will contains $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$) - the indices 2 machines that are connected by the $i$-th edge and the weight of it.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$ and the sum of $m$ over all test cases does not exceed $250 000$. The graph in each test case is guaranteed to be connected, no self-loops, but it can contain multiple edges.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

第一行包含 $n$ 和 $m$（$2 \le n \le 500$，$n - 1 \le m \le 250\,000$），分别表示节点数和导线数。

接下来的 $m$ 行中，第 $i$ 行包含 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$）——表示第 $i$ 条边所连接的两个机器的编号及其权重。

保证所有测试用例的 $n$ 之和不超过 $500$，所有测试用例的 $m$ 之和不超过 $250\,000$。每个测试用例中的图均保证连通、无自环，但可能包含重边。

For each test case, output one integer denotes the least amount of time needed to transfer the large package from machine $1$ to $n$.

对于每个测试用例，输出一个整数，表示将大包裹从机器 $1$ 传输到机器 $n$ 所需的最少时间。

Here is the graph in the first test case in the sample input:

Ela can ask the Wiring Wizard to use his spell on wire with the index of $7$, which is connecting machines $2$ and $3$. Then, since the machine $8$ is connected to machine $3$, the Wiring Wizard can disconnect wire $7$ from machine $3$ and connect it to machine $8$ in $3$ microseconds (weight of wire $3$).

After that, the package can be sent from machine $1$ to machine $8$ in $6$ microseconds. Therefore, the answer is $3 + 6 = 9$ microseconds.

Here is the graph in the third test case in the sample input:

以下是样例输入中第一个测试用例的图：

Ela 可请求 Wiring Wizard 对编号为 $7$ 的导线（连接机器 $2$ 和 $3$）施放法术。随后，由于机器 $8$ 与机器 $3$ 相连，Wiring Wizard 可将导线 $7$ 从机器 $3$ 上断开，并将其连接至机器 $8$，耗时 $3$ 微秒（即导线 $3$ 的权值）。

此后，包裹可从机器 $1$ 发送至机器 $8$，耗时 $6$ 微秒。因此，答案为 $3 + 6 = 9$ 微秒。

以下是样例输入中第三个测试用例的图：