Trong một thành phố sôi động, các con đường nối liền những khu phố tạo thành một mạng lưới phức tạp. Bạn được giao nhiệm vụ xây dựng bản đồ chi tiết thể hiện khoảng cách ngắn nhất giữa mọi cặp điểm trong thành phố. Thành phố được biểu diễn bởi một đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Mỗi cạnh được mô tả bởi 3 số nguyên ~u~, ~v~, ~w~ cho biết có một con đường hai chiều nối giữa đỉnh ~u~ và đỉnh ~v~ với trọng số ~w~. Nhiệm vụ của bạn là tính khoảng cách ngắn nhất từ mỗi đỉnh đến các đỉnh còn lại. Nếu không tồn tại đường đi giữa hai đỉnh nào đó, in ra ~-1~ cho vị trí đó. Cuối cùng, in ra ma trận ~N \times N~ với mỗi hàng bắt đầu bằng số thứ tự hàng kèm dấu ':' theo đúng định dạng yêu cầu.

Input

• Dòng ~1~: Gồm hai số nguyên ~N~ và ~M~ ~(N \leq 500, M~ < ~N×N~).
• ~M~ dòng tiếp theo: Mỗi dòng gồm ~3~ số nguyên ~u, v, w~.

Output

• In ra ma trận ~N \times N~. Mỗi hàng bắt đầu bằng số thứ tự hàng và dấu : theo sau đó là các khoảng cách ngắn nhất từ đỉnh tương ứng đến các đỉnh khác; nếu không có đường đi, in ra ~-1~.

Sample Input

10 20
6 8 5
8 7 6
2 5 3
5 9 14
2 8 5
5 4 1
5 7 5
9 10 15
7 10 2
6 7 7
7 3 8
3 8 4
3 2 4
7 4 3
4 9 10
3 5 1
9 1 1
9 8 10
6 1 1
10 1 10

Sample Output

1 : 0 11 10 11 11 1 8 6 1 10 
2 : 11 0 4 4 3 10 7 5 12 9 
3 : 10 4 0 2 1 9 5 4 11 7 
4 : 11 4 2 0 1 10 3 6 10 5 
5 : 11 3 1 1 0 10 4 5 11 6 
6 : 1 10 9 10 10 0 7 5 2 9 
7 : 8 7 5 3 4 7 0 6 9 2 
8 : 6 5 4 6 5 5 6 0 7 8 
9 : 1 12 11 10 11 2 9 7 0 11 
10 : 10 9 7 5 6 9 2 8 11 0