# Problem B

K-Walks

It is the final team contest. After some persuasion from his
fellow problem setters, *Lord Pooty* decided to make an
easy problem. Today, he was thinking about shortest path
problems. It is a classic problem with many variants. Today, he
decided to ask you on one interesting variant (in set-theoretic
notation!!).

Consider finite sets $S_1$ and $S_2 \subseteq \{ s \subseteq S_1: |s| = 2\} $, $K \in \mathbb {N}$, $f \in {\mathbb {N}}^{S_2}$.

Define:

\begin{align*} T\colon S_1 \times S_1 \to & \mathcal{P}(\mathbb {Z}_{\geq 0}) \\ (i,j) \mapsto & \{ x \in \mathbb {Z}_{\geq 0}\colon (\exists B \in S_2^{< \omega }) [ (\exists A \in S_1^{|B| + 1})[(B_ k = \{ A_{k}, A_{k+1}\} \forall k \in \mathbb {N}, k \leq |B|) \\ & \land (A_1 = i) \land (A_{|B|+1} = j)] \land (\sum _{b \in B}f(b) = x)] \land (K|x)\} \\ H\colon \mathcal{P} (\mathbb {Z}_{\geq 0})\to & \mathbb {Z}_{\geq -1} \\ X \mapsto & \left\{ \begin{array}{ll} \min (X) & \mbox{if } X \neq \emptyset \\ -1 & \mbox{if }X = \emptyset \end{array} \right. \end{align*}$\forall i,j\in S_1$,
output $H\circ
T(i,j)$.

In most circumstances, you are expected to understand the
abstract nonsense above which is more than sufficient to answer
the question. However, *Lord Pooty* is benevolent. As
such, he has provided to you the readable but mostly accurate
translation below:

**You are given a undirected simple
weighted graph with integer edge weights that is not
necessarily connected. Print the length of the K-walk (shortest
finite walk ^{1} where the total edge weight is a
multiple of $K$) from one
vertex to another if it exists, or $-1$ otherwise. Do this for all pairs
of vertices.**

## Input

The first line contains integers $V, E, K$. ($1 \leq V \leq 100$), ($0 \leq E \leq \min (200, \frac{V*(V-1)}{2}$), ($1 \leq K \leq 2^{63} -1$).

This is followed by $E$
lines: $u, v, w$
($1 \leq u,v \leq V$),
($1 \leq w \leq 200$).
This denotes a undirected edge from $u$ to $v$ of weight $w$. **Furthermore,
the sum of all edge weights is at most $200$.**

## Output

Output $V$ lines of $V$ integers, where the $j$ number of the $i$ line refers to the length of the $K$-walk from $i$ to $j$. Since the numbers can be huge, output up to the last $7$ digits for each integer where there exist K-walk or $-1$ otherwise.

Sample Input 1 | Sample Output 1 |
---|---|

3 2 1 1 2 2 2 3 1 |
0 2 3 2 0 1 3 1 0 |

Sample Input 2 | Sample Output 2 |
---|---|

2 1 9223372036854775807 1 2 2 |
0 9551614 9551614 0 |

Sample Input 3 | Sample Output 3 |
---|---|

3 2 10 1 2 15 2 3 15 |
0 -1 30 -1 0 -1 30 -1 0 |

**Footnotes**

- Intuitively, you can think of a walk as a path with repeated vertices or edges. However strictly speaking this is wrong as a path is a subset of a walk (not the other way around!) which does not have repeated vertices or edges.