Даний орієнтований граф, у якому можуть бути кратні ребра та петлі. Кожне ребро має вагу, що виражається цілим числом (можливо відʼємним). Гарантується, що цикли негативної ваги відсутні.

Потрібно порахувати довжини найкоротших шляхів від вершини номер 1 до решти вершин.

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

Програма отримує спочатку число \(N\) \((1 \le N \le 100)\) – кількість вершин графа та число \(M\) \((0 \le M \le 10000)\) – кількість ребер.

У наступних рядках йде \(M\) трійок чисел, що описують ребра: початок ребра, кінець ребра та вага (вага – ціле число від -100 до 100).

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

Програма має вивести \(N\) чисел – відстані від вершини номер 1 до всіх вершин графа. Якщо шляху до відповідної вершини немає, замість довжини шляху виведіть число 30000.

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

6 4
1 2 10
2 3 10
1 3 100
4 5 -10

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

0 10 20 30000 30000 30000