// problem #81

플로이드

n개 도시와 m개의 버스가 있다. 각 버스는 도시 a→b 로 비용 c가 든다. 모든 도시 쌍의 최소 비용을 구하시오. 갈 수 없으면 0.

입력

첫 줄 도시 수 n, 둘째 줄 버스 수 m, 이후 m개 줄에 a b c.

출력

n×n 행렬. i행 j열은 i→j 최소 비용(불가 0).

제한

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100,000
• 1 ≤ c ≤ 100,000

예제

3
4
1 2 5
1 3 8
2 3 2
3 1 3

0 5 7
5 0 2
3 8 0