{"raw_statement":[{"iden":"background","content":"请注意：**本题不是矩阵快速幂模板题**。"},{"iden":"statement","content":"给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。\n\n路径权值的定义是路径上所有边的权值之和。"},{"iden":"input","content":"第一行一个整数 $S$ 表示子任务编号。\n\n第二行一个整数 $T$ 表示数据组数。\n\n对于每组数据：\n\n- 第一行三个整数 $n, m, k$。\n- 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。"},{"iden":"output","content":"对于每组数据，输出一行 $n$ 个由空格隔开的整数表示答案。"},{"iden":"note","content":"- Subtask #1（$10$ 分）：$\\sum n ^ 3\\leq 10 ^ 6$，$k\\leq 10 ^ {18}$。\n- Subtask #2（$15$ 分）：$m = 2n - 2$，且对任意 $1\\leq i < n$，存在权值相等的 $(i, i + 1)$ 和 $(i + 1, i)$。\n- Subtask #3（$20$ 分）：$m\\geq 2n - 2$，且对任意 $(u, v)$，存在权值相等的 $(v, u)$，注意 $u$ 可以等于 $v$。依赖于 Subtask #2。\n- Subtask #4（$15$ 分）：$\\sum n ^ 3\\leq 10 ^ 6$，依赖于 Subtask #1。\n- Subtask #5（$15$ 分）：$k\\leq 10 ^ {18}$，依赖于 Subtask #1。\n- Subtask #6（$25$ 分）：无特殊性质。依赖于 Subtask #3，#4，#5。\n\n对于所有数据，$1\\leq S\\leq 6$，$1\\leq T\\leq 10 ^ 4$，$2\\leq n\\leq 300$，$1\\leq m\\leq 2n$，$1\\leq k\\leq 10 ^ {64}$，$1\\leq u, v\\leq n$，$1\\leq w\\leq 10 ^ {18}$。保证 $\\sum n \\leq 2\\times 10 ^ 5$ 且 $\\sum n ^ 3 \\leq 2.7 \\times 10 ^ 7$。\n\n题解在附件 `paper.pdf` 中。"}],"translated_statement":null,"sample_group":[["1\n1\n5 5 101\n1 2 1\n2 3 100\n3 4 10000\n4 2 1000000\n2 5 10\n","-1 -1 33333401 -1 33333311\n"],["见下发文件 ex_matrix1.in","见下发文件 ex_matrix1.ans"],["见下发文件 ex_matrix2.in","见下发文件 ex_matrix2.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}