CF1737D Ela and the Wiring Wizard

Ela 需要将一个大包裹从机器 $1$ 发送到机器 $n$，通过一组机器组成的网络。当前的网络状况下，她抱怨网络太慢，包裹无法及时送达。幸运的是，一位“布线巫师”愿意帮助她。 该网络可以表示为一个无向连通图，有 $n$ 个节点，每个节点代表一台机器。它们之间通过 $m$ 根线缆连接。第 $i$ 根线缆连接机器 $u_i$ 和 $v_i$，权值为 $w_i$。上述的大包裹如果通过第 $i$ 根线缆传输，将会从机器 $u_i$ 传到 $v_i$（或反之），耗时恰好为 $w_i$ 微秒。布线巫师可以任意多次使用他的法术。每次法术，他会选择编号为 $i$ 的线缆，连接机器 $u_i$ 和 $v_i$，并按如下步骤重新布线： - 选择该线缆连接的其中一台机器。无妨地，假设选择 $v_i$。 - 选择当前与 $v_i$ 相连的一台机器（包括 $u_i$），记为 $t_i$。将编号为 $i$ 的线缆从 $v_i$ 断开，然后用它连接 $u_i$ 和 $t_i$。 重新布线第 $i$ 根线缆需要 $w_i$ 微秒，线缆的权值在操作后不会改变。重新布线后，一台机器可能会有线缆连接到自身。此外，布线巫师警告 Ela，重新布线可能会导致部分机器暂时断开连接，但 Ela 并不在意。她的目标是让大包裹从机器 $1$ 以最快速度送到机器 $n$。注意，一旦包裹开始从机器 $1$ 传输，布线巫师就不能再移动线缆了。 Ela 想知道，在布线巫师的帮助下，将大包裹从机器 $1$ 送到机器 $n$ 所需的最少时间是多少。

每组测试数据包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。每组测试用例描述如下。 第一行包含 $n$ 和 $m$（$2 \le n \le 500$，$n-1 \le m \le 250\,000$），分别表示节点数和线缆数。 接下来的 $m$ 行，每行包含 $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$。每组测试用例中的图保证连通，无自环，但可以有重边。

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

以下是样例输入第一组测试数据对应的图： Ela 可以让布线巫师对编号为 $7$ 的线缆施法，该线缆连接机器 $2$ 和 $3$。由于机器 $8$ 与机器 $3$ 相连，巫师可以将第 $7$ 根线缆从 $3$ 断开，连接到 $8$，耗时 $3$ 微秒（线缆权值为 $3$）。 之后，包裹可以从机器 $1$ 传送到机器 $8$，耗时 $6$ 微秒。因此，答案为 $3 + 6 = 9$ 微秒。 以下是样例输入第三组测试数据对应的图：  由 ChatGPT 4.1 翻译