E.仙人掌交响曲

给你一个无向连接图，在这个图中，任何两个不同的简单循环没有共同的顶点。由于该图可能非常大，因此我们将以压缩的形式提供给你：对于每一条边，我们都会提供一个数字 $d$ ，表示这条边上有 $d$ 个额外的顶点。

您需要为图中的每个顶点和每条边分配一个权重--一个从 $1$ 到 $3$ 的整数。

如果相邻顶点权重的 bitwise XOR不等于 $0$ ，且不等于该边的权重，则称该图的一条边为良好边。

同样，如果图中某顶点相邻边的权重的比特XOR不等于 $0$ ，且不等于该顶点的权重，则该顶点称为良好顶点。

您需要确定有多少种为图的顶点和边分配权重的方法，从而使所有顶点和边都是好的。由于答案可能很大，因此需要计算答案除以 $998\,244\,353$ 的余数。

输入

第一行包含两个整数 n 和 m

• 图形中的顶点数量和边的数量( 2≤n≤5⋅105 , n−1≤m≤106 )。

接下来的每 m 行包含三个整数 ai,bi 和 di ( 1≤ai,bi≤n 、 ai≠bi 、 0≤di≤109 )，表示图中有一条边连接顶点 ai 和 bi 。此外，在这条边上还有 di 个额外的顶点。可以保证给定的图形是连通的，没有多条边，没有循环，并且图形中任何两个不同的简单循环没有共同的顶点。

输出

输出一个整数 - 问题的答案取模 998244353 。