题目描述

给定一张包含 $n$ 个点与 $m$ 条边的带权无向图 $G$，结点依次以 $1, 2, \dots, n$ 编号。

对于 $G$ 中两个不同的点 $u, v$（$1\leq u, v\leq n$），记 $d_{uv}$ 为二者之间异或最短路的长度。特殊地，若 $u, v$ 之间不连通则认为 $d_{uv} = 0$。注意异或最短路可以不为简单路。

试求 $G$ 中所有点对间异或最短路的长度和，即 $\sum_{u=1}^n\sum_{v=1}^n d_{uv}$。由于答案可能很大，你只需要输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行，两个正整数 $n, m$，表示 $G$ 中的点数与边数。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，表示 $G$ 中一条连接点 $u_i$ 与点 $v_i$，边权为 $w_i$ 的无向边。

$G$ 中可能包含重边与自环。

输出格式

一行，一个整数，表示 $G$ 中所有点对间异或最短路的长度和对 $998\,244\,353$ 取模的结果。

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

36

提示

保证 $1\leq n\leq 2\times 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq u_i, v_i\leq n$，$0\leq w_i< 2^{30}$。