L. Lazy Mayor
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Example
Input
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.