# [集训队互测 2023] 矩阵快速幂

## 题目背景

请注意：**本题不是矩阵快速幂模板题**。

## 题目描述

给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。

路径权值的定义是路径上所有边的权值之和。

## 输入格式

第一行一个整数 $S$ 表示子任务编号。

第二行一个整数 $T$ 表示数据组数。

对于每组数据：

- 第一行三个整数 $n, m, k$。
- 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。

## 输出格式

对于每组数据，输出一行 $n$ 个由空格隔开的整数表示答案。

## 样例 #1

### 样例输入 #1

```
1
1
5 5 101
1 2 1
2 3 100
3 4 10000
4 2 1000000
2 5 10
```

### 样例输出 #1

```
-1 -1 33333401 -1 33333311
```

## 样例 #2

### 样例输入 #2

```
见下发文件 ex_matrix1.in
```

### 样例输出 #2

```
见下发文件 ex_matrix1.ans
```

## 样例 #3

### 样例输入 #3

```
见下发文件 ex_matrix2.in
```

### 样例输出 #3

```
见下发文件 ex_matrix2.ans
```

## 提示

- Subtask #1（$10$ 分）：$\sum n ^ 3\leq 10 ^ 6$，$k\leq 10 ^ {18}$。
- Subtask #2（$15$ 分）：$m = 2n - 2$，且对任意 $1\leq i < n$，存在权值相等的 $(i, i + 1)$ 和 $(i + 1, i)$。
- Subtask #3（$20$ 分）：$m\geq 2n - 2$，且对任意 $(u, v)$，存在权值相等的 $(v, u)$，注意 $u$ 可以等于 $v$。依赖于 Subtask #2。
- Subtask #4（$15$ 分）：$\sum n ^ 3\leq 10 ^ 6$，依赖于 Subtask #1。
- Subtask #5（$15$ 分）：$k\leq 10 ^ {18}$，依赖于 Subtask #1。
- Subtask #6（$25$ 分）：无特殊性质。依赖于 Subtask #3，#4，#5。

对于所有数据，$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$。

题解在附件 `paper.pdf` 中。