Floyd

Interview

Time limit1sMemory limit256 MB

Summary

For every pair of n cities, compute the cheapest directed bus fare from up to 100,000 routes and print 0 where no route connects them.

Level: Medium4 of 10
Topics: Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

There are n cities (2 ≤ n ≤ 100) and m buses (1 ≤ m ≤ 100,000). Each bus leaves one city and arrives at another city, and riding it once costs a fixed amount.

Write a program that finds, for every pair of cities (A, B), the minimum cost of going from city A to city B.

Input

The first line has the number of cities n. The second line has the number of buses m. Each of the next m lines, that is lines 3 through m+2, describes one bus: its start city a, its destination city b, and the cost c of riding it once. No bus starts and ends at the same city. The cost is a natural number no larger than 100,000.

More than one bus route can connect the same start city and destination city.

Output

Print n lines. The j-th number on the i-th line is the minimum cost of going from city i to city j. If city j cannot be reached from city i, print 0 in that position. Separate the numbers on a line with a single space.

Examples3

Example 1

Input

Expected output

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

Example 2
Input
```
2
1
1 2 5
```
Expected output
```
0 5
0 0
```
Example 3
Input
```
2
3
1 2 7
2 1 3
1 2 4
```
Expected output
```
0 4
3 0
```