知识渊博，最聪慧的兽人就是上白泽慧音。她提醒未来的灾难，指导正确方向的妖怪。她住在人类村落，开一间寺子屋。每天都在编纂历史。

历史由若干关键节点构成，节点间的联系错综复杂，且每条联系各自的必然程度，而且可能与自身发生联系(考虑轮回)。为了更好地改写历史，上白泽慧音需要洞悉所有的联系链上的必然程度。

给定可能带自环、重边的有向加权图。定义长为 $k$ 的路径是恰好包含 $k$ 条边的、点和边都可重复的路径。两条路径不同当且仅当至少有一个点或一条边不一样。

设有 $n$ 个点，编号从 $1$ 开始。长为 $k$ 的路径的点序列为 $v_0,v_1,\cdots, v_k$，边为 $(v_0,v_1),(v_1,v_2),\cdots,(v_{k-1},v_k)$。定义一条边 $(u,v)$ 的边权为 $w_{(u,v)}$，则这条路径的权为 $\sum_{k=1}^nw_{(v_{i-1},v_i)}$。

记所有起点为 $v_0=i$，终点为 $v_k=j$ 的长为 $k$ 的路径的权值和为 $r_{i,j,k}$，并记 $s_{i,j,k}=\sum_{l=1}^kr_{i,j,l}$。你需要求出所有的 $s_{i,j,k}$。答案可能很大，故对 $998244353$ 取模。

输入一行三个整数 $n,m,k(1\le n\le 50,0\le m\le 10^5,0\le k\le 10^9)$。$n,m$ 分别代表点数、边数。

接下来输入 $m$ 行，每行三个整数 $u,v,w(1\le u,v\le n,0\le w\le 10^9)$，代表一条有向边 $(u,v)$ 的权为 $w_{(u,v)}$。

输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数代表 $s_{i,j,k}\bmod 998244353$。