Военный штаб расположен в опорном пункте с номером 1. Между опорными пунктами проложены направленные дороги, каждая из которых требует определённое время на прохед.

Известно расположение всех дорог между n опорными пунктами. Требуется для каждого опорного пункта определить минимальное время, за которое можно добраться до него из штаба.

Если до некоторого опорного пункта из штаба добраться невозможно, для него нужно вывести -1.

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

В первой строке заданы два целых числа n и m — количество опорных пунктов и количество дорог.

В следующих m строках содержатся описания дорог в формате u v w: из опорного пункта u можно проехать в опорный пункт v за w единиц времени.

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

Выведите n целых чисел — минимальные времена пути от штаба в пункте 1 до опорных пунктов 1, 2, ..., n в этом порядке.

Для недостижимых опорных пунктов выведите -1.

Ограничения

• 1 <= n <= 100000
• 0 <= m <= 300000
• 1 <= u, v <= n
• 0 <= w <= 1000000

Примеры

Пример 1

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

1 0

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

0

Пример 2

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

5 4
1 2 5
1 3 0
3 2 1
2 4 2

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

0 1 0 3 -1