All Pairs Shortest Routes

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

For every pair of cities (i, j), find the minimum cost of traveling from city i to city j and the route that spends exactly that cost.

The first line contains the number of cities n. The second line contains the number of buses m. Each of the next m lines describes one bus with three integers separated by spaces: the departure city a, the arrival city b, and the cost c of riding it once. No bus departs from and arrives at the same city, and several buses can connect the same pair of cities. The cost is a natural number not greater than 100,000.

First print n lines. The j-th number on the i-th line is the minimum cost of going from city i to city j. Print 0 in that position when city j is not reachable from city i, and print 0 when i and j are the same.

Then print $n \times n$ lines. They correspond to the pairs (i, j) ordered by i from 1 to n and, for each i, by j from 1 to n. On each line print the number of cities k on the minimum cost route from city i to city j, then the numbers of the cities on that route in the order they are visited, separated by spaces. City i and city j belong to the route. Print a single 0 on that line when city j is not reachable from city i or when i and j are the same.

When several routes have the minimum cost, print the one whose sequence of city numbers is smallest in lexicographic order. Two sequences are compared position by position, and if one of them equals the beginning of the other, the shorter one comes first.