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).
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 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.
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.
## 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.
[samples]
## 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.
**Definitions**
Let $ N, M, K \in \mathbb{Z} $ with $ 0 \leq N \leq 150 $, $ 0 \leq K \leq 10^9 $.
Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, N\} $ and $ E \subseteq V \times V $, $ |E| = M $.
Each edge $ (u, v) \in E $ has a weight $ w(u, v) \in \mathbb{Z} $, $ -10^6 \leq w(u, v) \leq 10^6 $.
Let $ A \in \mathbb{Z}^{N \times N} $ be the adjacency matrix where $ A_{u,v} = w(u,v) $ if $ (u,v) \in E $, and $ A_{u,v} = \infty $ otherwise (with $ A_{u,u} = \infty $ for all $ u $).
**Constraints**
1. $ 0 \leq N \leq 150 $, $ 0 \leq K \leq 10^9 $
2. Each pair of nodes has at most one edge.
3. Edge weights are integers in $ [-10^6, 10^6] $.
4. No self-loops: $ A_{u,u} = \infty $ for all $ u $.
**Objective**
For each ordered pair $ (i, j) \in V \times V $, compute:
- $ d_{i,j}^{(K)} $: the minimum total fatigue over all walks of exactly $ K $ edges from $ i $ to $ j $, or $ \infty $ if no such walk exists.
- $ c_{i,j}^{(K)} $: the number of walks of exactly $ K $ edges from $ i $ to $ j $ achieving $ d_{i,j}^{(K)} $, modulo $ 10^9 + 7 $, or $ 0 $ if no such walk exists.
Compute and output for each $ i \in \{1, \dots, N\} $:
$$
\left( d_{i,1}^{(K)}, c_{i,1}^{(K)} \right), \left( d_{i,2}^{(K)}, c_{i,2}^{(K)} \right), \dots, \left( d_{i,N}^{(K)}, c_{i,N}^{(K)} \right)
$$
where values are output as:
- If $ d_{i,j}^{(K)} = \infty $, output "inf" for fatigue and $ 0 $ for count.
- Otherwise, output $ d_{i,j}^{(K)} $ and $ c_{i,j}^{(K)} \mod (10^9 + 7) $.
**Note**: This is equivalent to computing the $ K $-th power of the (min, +) semiring matrix with counting, over the graph $ G $.