402828: GYM100889 L Lazy Mayor

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Lazy Mayortime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 (109 + 7).

Input

First line contains N, M and K(0 ≤ N ≤ 150, and 0 ≤ K ≤ 109). Next M lines consists of description of all the roads; ith line has three integers u, v and w(1 ≤ u, v ≤ N and  - 106 ≤ w ≤ 106) 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

Output N lines, each containing 2 * N numbers. In the ith 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 109 + 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.

ExampleInput
3 3 1
1 2 1
2 3 1
3 1 1
Output
X 0 1 1 1 1 
1 1 X 0 1 1
1 1 1 1 X 0
Note

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.

加入题单

上一题 下一题 算法标签: