G. ОМГраф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный связный взвешенный граф. Определим стоимость пути длины $$$k$$$ следующим образом:

  • Пусть веса всех рёбер на пути равны $$$w_1,...,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(2 \cdot 10^5, \frac{n(n - 1)}{2})$$$).

Следующие $$$m$$$ строк содержат целые числа $$$u, v$$$ и $$$w$$$ ($$$1 \le u, v \le n, 1 \le w \le 10^9$$$), представляющие ребро из вершины $$$u$$$ в $$$v$$$ с весом $$$w$$$. Гарантируется, что граф не содержит петель или кратных рёбер, и полученный граф связен.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$ и что сумма $$$m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, минимальную стоимость пути от вершины $$$1$$$ до $$$n$$$.

Пример
Входные данные
4
3 2
1 2 1
2 3 1
3 2
1 3 13
1 2 5
8 9
1 2 6
2 3 5
3 8 6
1 4 7
4 5 4
5 8 7
1 6 5
6 7 5
7 8 5
3 3
1 3 9
1 2 8
2 3 3
Выходные данные
2
18
10
11
Примечание

Для второго набора входных данных оптимальный путь это $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$, веса рёбер равны $$$5, 5, 13$$$, так что стоимость равна $$$\min(5, 5, 13) + \max(5, 5, 13) = 5 + 13 = 18$$$. Можно доказать, что нет пути с меньшей стоимостью.