Задан неориентированный взвешенный связный граф, состоящий из \(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-1\) целых чисел — минимальный вес пути от \(1\)-й вершины до \(i\)-й вершины для каждого \(i\) (\(2 \le i \le n\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
5 3 4
2 1 1
3 2 2
2 4 2
|
1 2 2 4
|
|
2
|
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
|
|
3
|
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
|