플로이드 워셜

문제

All-Pairs Shortest Path (APSP) 문제란 $1$부터 $N$까지 순서대로 번호가 매겨져 있는 $N$개의 정점과 두 정점을 연결하는 $M$개의 단방향 간선이 주어질 때, 모든 정점 쌍 ($i, j$)에 대해서 $i$에서 $j$로 가는 최단 거리를 구하는 문제다. APSP 문제를 해결해 보자.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2\le N\le 200; 1\le M\le 100\,000$)

둘째 줄부터 $M$개의 줄에 걸쳐, 각 줄에 간선 정보를 의미하는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $u$번 정점에서 $v$번 정점으로 가는 가중치가 $w$인 간선이 존재한다는 의미다. ($1\le u, v\le N; |w| \le 10\,000$)

음수 사이클은 존재하지 않음이 보장된다.

출력

$N\times N$ 크기의 격자를 출력한다. 즉, $N$개의 줄에 걸쳐 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번 줄의 $j$번째 정수는 $i$번 정점에서 $j$번 정점으로 가는 최단 거리를 의미한다. 만약 최단 거리가 존재하지 않는다면 대신 INF를 출력한다.

예제 입력 1

4 7
1 2 1
2 3 5
3 1 -2
1 3 8
1 2 3
3 2 8
3 4 1

예제 출력 1

0 1 6 7
3 0 5 6
-2 -1 0 1
INF INF INF 0