Under construction

Still being built. Things may change

Parcel Routing

Interview

Time limit2sMemory limit128 MB

Summary
Given a weighted graph, compute for every pair of hubs the next hub to visit on a shortest path using all-pairs shortest paths.
Level

Medium4 of 10

Topics
Shortest path, Graph, Dynamic programming, Matrix
Solved
No attempts yet

Problem

A delivery company has several collection hubs. Cargo can move between some pairs of hubs, and each route has a travel time.

For every ordered pair of different hubs, the company wants a route table that says which hub should be visited first when sending cargo along a shortest path. Rows are starting hubs and columns are destination hubs. If the entry in row r, column c is x, then cargo sent from hub r to hub c should first move to hub x.

Write a program that prints this route table.

Input

The first line contains two integers n and m.

  • n is the number of hubs, where 1 <= n <= 200.
  • m is the number of bidirectional routes, where 1 <= m <= 10000.

Each of the next m lines contains three integers a, b, and t, meaning that cargo can move between hubs a and b in t time. All hub numbers and route times are positive integers no greater than 1000.

Output

Print n lines containing the route table. The j-th value on the i-th line is the first hub to visit on a shortest path from hub i to hub j. If i = j, print -. Separate values on each line with one space.

Examples1

  1. Example 1

    Input
    6 10
1 2 2
1 3 1
2 4 5
2 5 3
2 6 7
3 4 4
3 5 6
3 6 7
4 6 4
5 6 2
    Expected output
    - 2 3 3 2 2
1 - 1 4 5 5
1 1 - 4 5 6
3 2 3 - 6 6
2 2 3 6 - 6
5 5 3 4 5 -