Có n thành phố và m con đường kết nối giữa chúng. Nhiệm vụ của bạn là xác định độ dài của con đường ngắn nhất từ thành phố 1 đến mọi thành phố.

Input

Dòng đầu tiên chứa hai số nguyên n và m: số thành phố và số con đường kết nối. Các thành phố được đánh số 1,2,...,n.

Sau đó có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: một con đường một chiều bắt đầu ở thành phố u, kết thúc ở thành phố v và có độ dài là w.

Output

In ra n số nguyên: độ dài tuyến đường ngắn nhất từ thành phố 1 đến các thành phố 1,2,...,n.

Hạn chế

~1 \le n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

~1 \le u, v \le n~

~1 \le w \le 10^9~

Examples

Input

6 9
1 2 6 
1 3 1
3 2 3 
3 5 2
2 4 8
4 5 1
5 4 3
4 6 1
5 6 10 

Output

0 4 1 6 3 7