图上极值和

题目描述

Orange有一张由 $n$ 个点 $m$ 条边构成的无向带权图。现在Orange想要从起点 $1$ 走到终点 $n$，且他想最小化经过边权的最大值和最小值之和。请你帮助他求出这个值。

输入格式

输入包含多组测试数据。 第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下： 第一行两个正整数 $n,m$，分别表示图中的点数和边数。
接下来 $m$ 行，每行三个正整数 $u\ v\ w$，表示图中的每一条边。

数据范围

$2 \leq n \leq 3 \times 10^5, 1 \leq m \leq 5 \times 10^5$ $1 \leq u,v \leq n, 1 \leq w \leq 10^9$ $\sum n \le 3\times 10^5, \sum m \le 5 \times 10^5$

输出格式

对于每组测试数据，在单独的一行输出一个整数，表示 $1$ 号到 $n$ 号点的最小极值和，如果不联通，请输出 -1。

样例 #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

样例输出 #1

3
6
2

提示

样例解释1

$1 \rightarrow 2 \rightarrow1\rightarrow3\rightarrow5$，其中最大边权是 $1 \rightarrow 3$ 或者 $3\rightarrow5$ 的 $2$，最小边权是 $1\rightarrow2$ 的 $1$，因此最小极值和为：$1+2=3$。