CF2117G.Omg Graph

给定一个带权无向连通图，定义一条长度为 $k$ 路径的费用如下：

• 设路径经过边的权值为 $w_1,w_2,\dots,w_k$。
• 路径的费用定义为 $(\min_{i=1}^k w_i) + (\max_{i=1}^k w_i)$，也就是最大的边权加上最小的边权。

请求出所有从结点 $1$ 到结点 $n$ 的路径中最小的费用。注意路径未必是简单路径。

输入数据包含多个测试用例。输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的个数。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$n-1 \le m \le \min\left(2 \cdot 10^5, \frac{n(n-1)}{2}\right)$）。
• 接下来的 $m$ 行中每行包含三个整数 $u$，$v$ 和 $w$（$1 \le u, v \le n$，$1 \le w \le 10^9$），表示一条从结点 $u$ 连接到结点 $v$，权值为 $w$ 的无向边。输入数据保证这些边组成一个连通图，且图中不含自环或重边。

输入数据保证所有测试用例的 $n$ 和 $m$ 之和均不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行一个整数，代表从结点 $1$ 到结点 $n$ 的最小费用。

对于第二个测试用例，最优路径之一是 $1 \rightarrow 2 \rightarrow 1 \rightarrow 3$。经过的边权分别为 $5,5,13$，因此费用为 $\min(5,5,13)+\max(5,5,13)=18$。可以证明不存在费用更低的路径。