CF1893E.Cacti Symphony

You are given an undirected connected graph in which any two distinct simple cycles do not have common vertices. Since the graph can be very large, it is given to you in a compressed form: for each edge, you are also given a number $d$, which indicates that there are $d$ additional vertices on this edge.

You need to assign a weight to each vertex and each edge of the graph — an integer from $1$ to $3$.

An edge of the graph is called good if the bitwise XOR of the weights of its adjacent vertices is not equal to $0$ and not equal to the weight of that edge.

Similarly, a vertex of the graph is called good if the bitwise XOR of the weights of its adjacent edges is not equal to $0$ and not equal to the weight of that vertex.

You need to determine how many ways there are to assign weights to the vertices and edges of the graph so that all vertices and edges are good. Since the answer can be quite large, you need to calculate the remainder of the answer divided by $998\,244\,353$.

给你一个无向连通图，其中任意两个不同的简单环没有公共顶点。由于该图可能非常大，它以压缩形式给出：对于每条边，你还被给定一个数 $d$，表示该边上存在 $d$ 个额外的顶点。

你需要为图中的每个顶点和每条边分配一个权值——取值为 $1$、$2$ 或 $3$ 的整数。

若一条边满足其相邻两个顶点的权值的按位异或结果既不等于 $0$，也不等于该边自身的权值，则称这条边为好边。

类似地，若一个顶点满足其所有关联边的权值的按位异或结果既不等于 $0$，也不等于该顶点自身的权值，则称这个顶点为好顶点。

你需要计算有多少种方式为图中所有顶点和边分配权值，使得图中所有顶点和边均为好顶点与好边。由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模的结果。

The first line contains two integers $n$ and $m$ — the number of vertices and the number of edges in the graph ($2 \le n \le 5 \cdot 10^5$, $n - 1 \le m \le 10^6$).

Each of the next $m$ lines contains three integers $a_i, b_i$, and $d_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $0 \le d_i \le 10^9$), indicating that there is an edge in the graph connecting vertices $a_i$ and $b_i$. Additionally, on this edge, there are $d_i$ additional vertices. It is guaranteed that the given graph is connected, there are no multiple edges, loops, and any two distinct simple cycles of the graph do not have common vertices.

第一行包含两个整数 $n$ 和 $m$ —— 分别表示图中的顶点数和边数（$2 \le n \le 5 \cdot 10^5$，$n - 1 \le m \le 10^6$）。

接下来的 $m$ 行中，每行包含三个整数 $a_i, b_i$ 和 $d_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$，$0 \le d_i \le 10^9$），表示图中存在一条连接顶点 $a_i$ 和 $b_i$ 的边；此外，该边上还额外存在 $d_i$ 个顶点。保证所给图是连通的，不存在重边、自环，且图中任意两条不同的简单环没有公共顶点。

Output a single integer — the answer to the problem modulo $998\,244\,353$.

输出一个整数——该问题答案对 $998\,244\,353$ 取模的结果。

In the first test, the graph is a simple cycle of $3$ vertices. It can be shown, that there are exactly $12$ ways to assign weights, to make all vertexes and edges good.

In the second test, the graph has the form of two simple cycles of $3$ vertices connected by an edge. It can be shown that for such a graph there are no ways to arrange weights so that all vertices and edges are good.

在第一个测试中，该图是一个包含 $3$ 个顶点的简单环。可以证明，恰好有 $12$ 种方式为边赋予权重，使得所有顶点和边均为“好”的。

在第二个测试中，该图由两个包含 $3$ 个顶点的简单环通过一条边连接而成。可以证明，对于这样的图，不存在任何一种权重分配方式，使得所有顶点和边均为“好”的。