Задан неориентированный взвешенный связный граф, состоящий из \(n\) вершин и \(m\) ребер. Гарантируется, что в данном графе нет петель и кратных ребер.
Определим вес пути, состоящего из \(k\) ребер с индексами \(e_1, e_2, \dots, e_k\) как \(\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}\), где \(w_i\) — вес \(i\)-го ребра в графе.
Ваша задача — для каждого \(i\) (\(2 \le i \le n\)) найти минимальный вес пути от \(1\)-й вершины до \(i\)-й вершины.
Первая строка содержит два целых числа \(n\) и \(m\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le m \le 2 \cdot 10^5\)) — количество вершин и количество ребер в графе.
Следующие \(m\) строк содержат по три целых числа \(v_i, u_i, w_i\) (\(1 \le v_i, u_i \le n\); \(1 \le w_i \le 10^9\); \(v_i \neq u_i\)) — концы \(i\)-го ребра и его вес соответственно.
Выведите \(n-1\) целых чисел — минимальный вес пути от \(1\)-й вершины до \(i\)-й вершины для каждого \(i\) (\(2 \le i \le n\)).
5 4 5 3 4 2 1 1 3 2 2 2 4 2
1 2 2 4
6 8 3 1 1 3 6 2 5 4 2 4 2 2 6 1 1 5 2 1 3 2 3 1 5 4
2 1 4 3 1
7 10 7 5 5 2 3 3 4 7 1 5 3 6 2 7 6 6 2 6 3 7 6 4 2 1 3 1 4 1 7 4
3 4 2 7 7 3
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач