Given a directed weighted graph with the possibility of having parallel edges, self-loops, and negative weights. The graph consists of $N$ nodes and $M$ directed edges. For every pair of nodes, determine the minimum distance achievable between them by traversing no more than $K$ directed edges, with the option of repeatedly passing through the same edge.

Formally speaking. Let edge $i$ go from node $u_i$ to $v_i$ with weight $w_i$. A path from $u$ to $v$ traversing $k$ edges is defined as an array $p$ of length $len_p = k$, where $1 \le p_i \le m, u_{p_1} = u, v_{p_k} = v, v_{p_i} = u_{p_{i + 1}}$ for $1 \le i < k$, and $dis_p = \sum_{i=1}^{k}w_{p_i}$ represents the distance of the path. For each $u$, $v$($1 \le u, v \le N $), you should calculate $\min_{p, len_p \le K}{dis_p}$.

The first line contains three integers: $N$, $M$, and $K (2 \le N \le 100, 1 \le M \le 10^4, 0 \le K \le 10^9)$.
The next $M$ lines each contain three integers: $u_i$, $v_i$, and $w_i$, indicating a directed edge from node $u_i$ to node $v_i$ with weight $w_i$ $(1 \le u_i, v_i \le N, -10^9 \le w_i \le 10^9)$.

Output an $N\times N$ matrix, where the element at row $i$ and column $j$ represents the minimum distance from node $i$ to node $j$ while traversing through at most $K$ edges. If it is not possible to reach node $j$ from node $i$, output "NO"(without quotes).