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

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

给定可能带自环、重边的有向加权图。定义长为 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。