플로이드-워셜

$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 양의 가중치 방향 간선으로 이루어진 그래프가 있다.

모든 정점 쌍 $(i,j)$에 대해 $i$번 정점에서 $j$번 정점으로 가는 최단 거리를 구하라.

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 400,\ 0 \leq M \leq 100\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 방향 간선을 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $(1 \leq u,v \leq N,\ u \neq v,\ 1 \leq w \leq 10^9)$

같은 방향 간선은 두 번 이상 주어지지 않는다.

$N$개의 줄에 걸쳐 모든 정점 쌍 사이의 최단 거리를 출력한다.

$i$번째 줄의 $j$번째 값에는 $i$번 정점에서 $j$번 정점으로 가는 최단 거리를 출력한다.

도달할 수 없는 경우에는 INF를 출력한다.