题目描述

坎格鲁斯普雷又给了你一个有 $n$ 个节点，$m$ 条边的无向图，每条边都有一个边权 $w$。保证这个图中无重边和自环。

但是这张图被施加了魔法，路径 $u → v$ 的权值被定义为这条路径上所有边的 边权的乘积。

现在坎格鲁斯普雷想让你求出从点 $1$ 到其它 $n-1$ 个点的路径的最小权值。如果两个点不可达，则答案为 $-1$ 。由于答案可能很大，最后需要输出对 $998244353$ 取模后的结果。

输入格式

第一行输入 $n,m$ 表示 $n(2\le n\le 10^5)$ 个点，$m(1 \le m\leq \min(\frac{n\cdot(n-1)}{2},10\cdot n))$ 条边。

接下来 $m$ 行每行输入 $u,v,w$，表示 节点$u$ 和 $v$ ($1<=u,v<=n$)之间有一条值为 $w \in \{1,2,4,8\}$ 的边权。保证 $u \neq v$ 。

输出格式

输出 $n-1$ 行，第 $i$ 行表示从 $1$ 号点到第 $i+1$ 行点的路径最小权值对 $998244353$ 取模后的结果。如果不可达，请输出 $-1$。

输入输出样例 #1

5 8
1 2 1
1 5 1
1 3 1
2 3 2
3 4 2
4 5 1
4 4 2
5 5 1

1
1
1
1

输入输出样例 #2

5 5
1 2 1
1 3 1
3 4 2
3 5 2
4 5 2

1
1
2
2

输入输出样例 #3

8 11
1 2 1
1 3 1
1 7 2
2 4 2
2 6 2
2 8 2
3 5 2
3 7 1
4 8 2
4 4 1
4 6 1

1
1
2
2
2
1
2