$N$개의 정점과 가중치 있는 $M$개의 간선으로 이루어진 유향 그래프 $G$가 주어진다. 모든 정점 쌍 최단 경로를 구해보자.

첫째 줄에 정점의 개수$N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 300; 1 ≤ M ≤ N(N-1))$

둘째 줄부터 $M$개의 줄에 걸쳐 $u, v, w$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N, u ≠ v; 1 ≤ w ≤ 1,000)$ 이는 정점 $u$에서 정점 $v$로 향하는 가중치 $w$의 간선이 존재한다는 의미이다. 각 간선은 고유하다.

출력은 $N$개의 줄에 걸쳐 이뤄진다. $i$번째 줄에는 $i$번 정점으로부터 $1, 2, ... , N$번 정점에 도달하는 최단 거리를 공백으로 구분하여 출력한다.

$i ≠ j$인 $i, j$에 대해 $i$에서 $j$에 도달하는 경로가 존재하지 않는다면 $-1$을 출력해야 한다.