Pondo Shortest Paths

Problem Statement

You are given a connected undirected graph with ~n~ vertices and ~m~ edges with weights. For all pairs of vertices, determine the shortest path between them.

Input Format

Your first line will contain two space-separated integers ~n~ and ~m~. Your next ~m~ lines will contain three integers each ~u~, ~v~ and ~w~ where ~u~ and ~v~ represent the endpoints of the edge and ~w~ represents the weight.

Output Format

You should output ~n~ lines. The ~i^{th}~ line should contain ~a[i][1], a[i][2], a[i][3], ..., a[i][n]~ all space-separated where ~a[u][v]~ is the shortest path from ~u~ to ~v~.

Constraints

• ~1 \leq n, u, v \leq 100~
• ~1 \leq m \leq \frac{n \cdot (n - 1)}{2}~
• ~1 \leq w \leq 100~

YOU CAN HAVE EDGES BETWEEN THE SAME NODES

Sample Cases

Input 1

4 5
1 2 5
1 3 9
2 3 1
4 2 3
3 4 2

Output 1

0 5 6 8
5 0 1 3
6 1 0 2
8 3 2 0

Template

n, m = map(int, input().split())
edges = [None] * m
for i in range(m):
    u, v, w = map(int, input().spilt())
    edges[i] = (u, v, w)

# print your output