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$$$。从 $$$v_i$$$ 断开索引为 $$$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$$$ 行,第 $$$i$$$ 行将包含 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) - 通过$$$i$$$-th 条边及其权重。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$250 000$$$。每个测试用例中的图都保证是连通的,没有自环,但可以包含多条边。
输出
对于每个测试用例,输出一个整数表示将大包从机器 $$$1$$$ 传输到 $$$n$$$ 所需的最短时间。
示例
输入 #1
3 8 9 1 2 3 6 4 5 3 5 6 6 1 3 7 4 4 3 8 4 2 3 3 7 8 5 4 5 2 4 5 1 2 1 2 4 1 3 4 1 3 1 1 1 3 2 8 8 4 6 92 7 1 65 6 5 43 6 7 96 4 3 74 4 8 54 7 4 99 2 5 22
输出 #1
9 2 154
注意
这是示例输入中第一个测试用例的图表:
Ela 可以要求接线向导在索引为 $$$7$$$ 的线路上使用他的咒语,该咒语连接机器 $$$2$$$ 和 $$$3$$$。然后,由于机器 $$$8$$$ 连接到机器 $$$3$$$,接线向导可以在 $$$3$$$ 微秒内从机器 $$$7$$$ 断开电线 $$$7$$$ 并将其连接到机器 $$$8$$$(电线重量 $$$3$$$)。
之后,包可以在$$$6$$$微秒内从机器$$$1$$$发送到机器$$$8$$$。因此,答案是 $$$3 + 6 = 9$$$ 微秒。
这是示例输入中第三个测试用例的图表: