10062 플로이드-워셜 Gold IV

문제

N개의 정점과 M개의 간선을 가진 방향 그래프에서, 모든 정점 쌍 사이의 최단 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 수 N (1 ≤ N ≤ 500)이 주어진다. 둘째 줄에 간선의 수 M (1 ≤ M ≤ N²)이 주어진다. 다음 M개의 줄에 u, v, w (u에서 v로 가중치 w)가 주어진다. (1 ≤ w ≤ 10,000)

출력

N개의 줄에 걸쳐 i번 정점에서 j번 정점으로의 최단 경로를 공백으로 구분하여 출력한다. 경로가 없으면 INF를 출력한다.

4
5
1 2 2
1 3 5
2 3 1
3 4 3
2 4 7

0 2 3 6
INF 0 1 4
INF INF 0 3
INF INF INF 0