Найкоротший шлях 2

Limits: 2 sec., 256 MiB

Дано зважений орієнтований граф, вершини якого пронумеровані числами від 1 до \(n\).

Знайдіть довжини найкоротших шляхів від вершини з номером 1 до кожної з \(n\) вершин графа.

Input

У першому рядку задано два цілих числа \(n\) та \(m\) — кількість вершин та ребер у графі відповідно.

У наступних \(m\) рядках задано по три цілих числа \(u\), \(v\) та \(w\) — номери початкової та кінцевої вершин ребра, а також вага ребра.

Output

В єдиному рядку виведіть довжини найкоротших шляхів від першої до кожної з \(n\) вершин через пробіл.

Якщо відстань до вершини рівна \(\infty\) або \(-\infty\), то виведіть inf або -inf відповідно. Інакше виведіть ціле число.

Constraints

\(2 \le n \le 2000\),

\(1 \le m \le \min\left(n \cdot (n - 1), 10^4\right)\),

\(1 \le u, v \le n\),

\(|w| \le 10^9\),

гарантується, що в графі не має петель і між кожною парою вершин у кожному напрямку є не більше ніж одне ребро.

Samples