小苯的奇怪最短路
题号：NC285971
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯正处于一个 n 个点 m 条边的无向图内的 1 号节点上，他想要走到 n 号点去。图中的每条边都有一些边权 w_i，但这个花费非常奇怪。

具体的，小苯走到 n 号点的花费为：他经过的边里，权值最大的边的权 + 权值最小的边的权。

请你帮他求出他从 1 走到 n 号点的最短路是多少吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 1000\right) 代表数据组数，每组测试数据描述如下：
第一行两个正整数 n\ m\ (2 \leq n \leq 3 \times 10^5, 1 \leq m \leq 5 \times 10^5)，分别表示图中的点数和边数。
接下来 m 行，每行三个正整数 u\ v\ w\ (1 \leq u,v \leq n, 1 \leq w \leq 10^9)，表示图中的每一条边。
（保证所有测试数据中，n 的总和不超过 3 \times 10^5，m 的总和不超过 5 \times 10^5。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数，表示 1 号到 n 号点的最短路，如果不联通，输出 -1 即可。
示例1

输入

复制 
3
5 6
1 2 1
1 3 2
1 4 3
3 5 2
2 5 4
4 5 3
6 7
1 2 1
1 3 100
1 4 100
3 6 1
4 6 2
2 5 5
5 6 2
2 1
1 2 1

输出

复制 
3
6
2

说明

这里给出样例一的图，实际行走路径为：
1 \rightarrow 2 \rightarrow1\rightarrow3\rightarrow5，其中最大边权是 1 \rightarrow 3 或者 3\rightarrow5 的 2，最小边权是 1\rightarrow2 的 1，因此最短路为：1+2=3。