402828: GYM100889 L Lazy Mayor

You have organized an event and for that you decorated the entire city, the City Mayor is the chief guest after all. You would like to show the Mayor around. But the Mayor is a picky person, he says he will travel exactly for K roads.

The City has N areas(numbered from 1 to N) and M undirected roads in total. You know the map and the fatigue value of each road, each pair of areas have at-most one road between them. You need to find for each pair of cities, what is the minimum fatigue value the Mayor will get if you show him around between that pair of cities, also you need to find out what are the number of ways in which the Mayor will get the minimum fatigue for that pair of city. Since the number of ways may be very large output it modulo (10⁹ + 7).

First line contains N, M and K(0 ≤ N ≤ 150, and 0 ≤ K ≤ 10⁹). Next M lines consists of description of all the roads; i^th line has three integers u, v and w(1 ≤ u, v ≤ N and  - 10⁶ ≤ w ≤ 10⁶) which means that there is a direct path between area u and area v and has a fatigue value of w(the paths are undirected).

Output N lines, each containing 2 * N numbers. In the i^th line, for each j(1 ≤ j ≤ N) output two integers: the minimum fatigue value if you start from i and go to j using exactly K roads; the number of ways to achieve that minimum fatigue value, modulo 10⁹ + 7. If there is no path between i and j, using exactly K edges, output character for fatigue value and 0 for number of ways.

3 3 1
1 2 1
2 3 1
3 1 1

X 0 1 1 1 1 
1 1 X 0 1 1 
1 1 1 1 X 0 

Note that there is no shortest path using one road from node i to node i, for all i.

For all other pair of nodes, there exist exactly one shortest path using one road.