L. Очередная задача про графы

В ориентированном графе стоят две руки: одна в вершине 1, другая в вершине $p$. За ход можно передвинуть одну руку по ребру, потратив его вес. Игра кончается, когда обе руки окажутся в одной вершине. Для каждого $p$ от 2 до $N$ найдите минимальное суммарное время.

В первой строке $N$ и $M$ ($2 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$). В каждой из следующих $M$ строк — числа $U_i$, $V_i$ и $W_i$ ($1 \le U_i, V_i \le N$, $U_i \ne V_i$, $1 \le W_i \le 10^9$) — ориентированное ребро из $U_i$ в $V_i$. Пары $(U_i, V_i)$ различны.

Выведите $N - 1$ число: для каждого $p$ от 2 до $N$ — минимальное время или $-1$.