Форд-Беллман

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

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

Вхідні дані

Спочатку задано кількість вершин графа n (1 ≤ n ≤ 100), далі йде кількість ребер m (0 ≤ m ≤ 10000). Наступні m трійок чисел описують ребра: початок ребра, кінець ребра та його вага (вага - ціле число від -100 до 100).

Вихідні дані

Виведіть n чисел - відстані від вершини номер 1 до всіх вершин графа. Якщо шляху до відповідної вершини не існує, замість довжини шляху виведіть число 30000.

Приклади