#2475. 「2018 集训队互测 Day 3」白云的旅行

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

白云开始了一段旅程。

旅途中一共有 nn 个城市,编号为 11nn,城市之间有一些道路相连。其道路结构可以抽象为一棵仙人掌。如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

what-is-cactus.png

白云对这些城市间的每条道路都有一个喜爱度。一条路径的喜爱度是其上所有道路的喜爱度的乘积。

现在白云在 11 号城市准备出发。为了制定合理的路线,白云会时不时问白兔:“从 11 号城市出发不经过重复道路到达 kk 号城市的所有路径喜爱度之和是多少?”

这可难倒了白兔,请你帮忙对于 k=1,2,,nk=1,2,\ldots,n 求出相应答案。只需要输出答案对998244353(=7×17×223+1,998244353( = 7\times 17\times 2^{23}+1,一个质数))取模后的值。

输入格式

11 行两个正整数 n,mn,m 表示城市的个数和道路的条数。保证 n2n \ge 2

接下来 mm 行每行两个正整数 v,u,w(1v,un,1w<998244353)v,u,w(1 \le v,u \le n,1 \le w < 998244353) 表示一条连接城市 vvuu 的喜爱度为 ww 的道路。

保证输入的图是一棵仙人掌,没有自环,但可能有重边。

输出格式

输出 nn 行,第 ii 行包含一个整数表示 k=ik=i 时的答案。

样例

样例输入 1

11 11
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
2 7 10
3 8 20
4 9 30
5 10 40
6 11 50

样例输出 1

3
2
2
2
2
2
20
40
60
80
100

样例解释 1

注意,两条路径不同为它们经过的边数不同或存在一个满足 1x1 \le x \le 路径长度 的 xx 使得这两条路径经过的第 xx 条边不同。

长度为00的路径也是合法路径,权值视为 11

数据范围与提示

对于所有数据,n105,1w<998244353n \le 10^5,1 \le w < 998244353

子任务编号 nn \leq ww \leq 其它约定
1 10510^5 11 m=n1m=n-1
2 10510^5 998244352998244352 m=n1m=n-1
3 88 998244352998244352
4 10510^5 11 一个点最多只在一个环中
5 10510^5 998244352998244352 一个点最多只在一个环中
6 500500 998244352998244352
7 30003000 11
8 30003000 998244352998244352
9 10510^5 11
10 10510^5 998244352998244352

虽然我没有给 mm 的范围,但是熟悉仙人掌的小朋友都知道对于仙人掌肯定满足 n1m2n2n-1 \le m \le 2n-2