Parcel Routing

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.

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.

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.