Cho một đồ thị có hướng có thể chứa nhiều cạnh và khuyên. Mỗi cạnh có một trọng số được biểu diễn bằng một số (có thể âm). Đảm bảo rằng không có chu trình nào có trọng số âm. Hãy tính độ dài của đường đi ngắn nhất từ đỉnh số 1 đến tất cả các đỉnh khác.

Dữ liệu vào

• Dòng đầu tiên: chứa \(n\) là số đỉnh \((1 \le n \le 100)\) và \(m\) là số cạnh \((0 \le m \le 10^4)\)
• \(m\) dòng tiếp theo, mỗi dòng chứa \(3\) số là mô tả của một cạnh \(u,v,w\): đường đi từ đỉnh \(u\) đến đỉnh \(v\) có trọng số là \(w\) \((|w| \le 100)\)

Dữ liệu ra

• In ra \(n\) số nguyên là khoảng cách từ đến \(1\) đến tất cả đỉnh còn lại trong đồ thị. Nếu không có đường đi thì in số \(30000\)

Input 1

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

Output 1

0 10 11 30000