编辑题目

【题目描述】

Alice 和 Bob 正在玩一个游戏。

他们有一张 $n$ 个点 $m$ 条边的无向连通图，每条边有边权。Alice 会先选择一条边 $E$ 和一个节点 $S$，分别作为基准边和起点。然后， Bob 需要从起点 $S$ 出发，每次沿着相邻的边移动，如果他能在不经过边 $E$ 的情况下，移动到某一条边权与 $E$ 相同的边，那么就判 Bob 胜，否则判 Alice 胜。

由于 Alice 还是位新手，所以她只会等概率的选择 $E$ 和 $S$。Bob 想知道，当他采用最优策略时，他获胜的概率是多少。答案对 $998244353$ 取模。

【输入格式】

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条连接节点 $u$ 和节点 $v$ 且边权为 $w$ 的边。

【输出格式】

一个整数，表示答案对 $998244353$ 取模后的值。

【样例输入】

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

【样例输出】

399297742

【样例说明】

概率为 $\frac{4}{5}$。

【样例下载】

样例下载

【数据规模与约定】

对于前 $30\%$ 的数据，保证 $1\le n,m\le 100$。 

对于前 $60\%$ 的数据，保证 $1\le n,m\le 5000$。 

另有 $10\%$ 的数据，保证 $w=1$。

对于 $100\%$ 的数据，保证 $1\le n,m\le 10^6,1\le w\le 10^9$。 

保证图连通且没有重边或自环。

【来源】

蒙德城算法竞赛 T2