Вам заданий опис мережі доріг країни в якій існує дві столиці (міста з номерами \(1\) та \(N\)).
Для кожної дороги відома ціна яку треба заплатити, щоб мати можливість їздити нею (після оплати - їздити відповідною дорогою можна необмежену кількість раз).
Для кожного міста визначіть - яку найменшу суму грошей треба витратити, щоб мати можливість доїжджати з цього міста до обох столиць (як до міста номер \(1\) так і до міста номер \(N\))

Формат вхідних даних

Перший рядок містить числа \(N\) та \(M\) (\(1 \le N \le 100000\), \(0 \le M \le 300000\)), де \(N\) - кількість міст\(, а M\) – кількість доріг.

Кожен з \(M\) наступних рядків містить опис двосторонньої дороги – три цілих числа \(V1\), \(V2\) та \(W\) (\(1 \le V1,V2 \le N\), \(1 \le W \le 10^6\)).
Це означає, що існує дорога ціною \(W\), між містами \(V1\) та \(V2\).

Формат вихідних даних

Виведіть \(N\) чисел через пробіл - відповідь на задачу для кожного міста.
Якщо з міста дістатись до обох столиць неможливо - виведіть для цього міста -1

Приклад вхідних даних

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

Приклад вихідних даних

6 9 6 7 14 6