1261: [STT2024JanR2+] 不可持久化动态无向图的无源汇全局任意割 2.0
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：4
题目描述
给定一张无向图 $G=(V,E)$，每条边有一个权值 $w(u,v)$，为割掉它的代价。一个任意割 $C$ 是原图边集 $E$ 的一个非空子集，删去后将生成一张新图 $G'=(V',E')$。定义一个割的代价为割掉边权值 $w(u,v)$ 的总和，即 $\rvert C \lvert=\sum_{(u,v)\in C} w(u,v)$。
现在询问整张图有多少种不同的代价，并且回答每种代价又有多少种方案，方案对 $998244353$ 取模。
现在询问整张图有多少种不同的代价，并且回答每种代价又有多少种方案，方案对 $998244353$ 取模。
输入
输入的第一行包含三个正整数 $N, M,$，表示结点个数，图上边的条数。
接下来 $m$ 行每行三个数字，$v_i,u_i$ 表示一条连接 $v_i$ 和 $u_i$，边权为 $w_i$ 的边。
接下来 $m$ 行每行三个数字，$v_i,u_i$ 表示一条连接 $v_i$ 和 $u_i$，边权为 $w_i$ 的边。
输出
第一行输出有多少种不同的代价，记这个数字为 $L$。
接下来 $L$ 行，每行两个数，第一个表示代价，第二个表示这个代价有多少种方案，按代价从小到大输出。
接下来 $L$ 行，每行两个数，第一个表示代价，第二个表示这个代价有多少种方案，按代价从小到大输出。
样例输入 复制
4 4
1 2 1
3 4 3
4 1 4
2 4 2样例输出 复制
10
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 1
9 1
10 1提示
### 样例 #2
#### 样例输入 #2
```
100000 1
2 4 8
```
#### 样例输出 #2
```
1
8 1
```
### 提示
**【样例 #1 解释】**
有 $1-2$，$2-4$，$1-4$，$3-4$ 四条边。
| 割掉边数 | 方案 $1$ |方案 $2$|方案 $3$|方案 $4$|方案 $5$ | 方案 $6$ |
| :-:| :-: | :-: | :-: | :-: | :-: | :-: |
| $1$ | 割掉 $1-2$，代价为 $1$ | 割掉 $2-4$，代价为 $2$ | 割掉 $3-4$，代价为 $3$ | 割掉 $1-4$，代价为 $4$ |||
| $2$ | 割掉 $1-2$ 和 $2-4$，代价为 $3$ | 割掉 $1-2$ 和 $3-4$，代价为 $4$ | 割掉 $1-2$ 和 $1-4$，代价为 $5$ | 割掉 $2-4$ 和 $3-4$，代价为 $5$ | 割掉 $2-4$ 和 $1-4$，代价为 $6$ | 割掉 $3-4$ 和 $1-4$，代价为 $7$ |
| $3$ | 除 $1-4$ 外都割掉，代价为 $6$ | 除 $3-4$ 外都割掉，代价为 $7$ | 除 $2-4$ 外都割掉，代价为 $8$ | 除 $1-2$ 外都割掉，代价为 $9$ |||
| $4$ | 全部割掉，代价为 $10$||||||
共 $10$ 种代价，$15$ 种方案。
**【样例 #2 解释】**
只有割掉 $1-2$ 这种方法，代价为 $8$。
**【数据范围】**
对于 $40\%$ 的数据，满足 $1 \leq n \leq 10$，$1 \leq m \leq 20$。
对于 $100\%$ 的数据，满足 $1 \leq n \leq 200$，$0 \leq m \leq 500$，$1 \leq w_i \leq 10$。