408538: GYM103182 G SigSegv

The forgotten country SigSegv of AGM consists of $$$N$$$ cities, connected with each other through $$$M$$$ bidirectional roads. The country has a very rich fauna, and hence, each road has an associated positive integer beauty value. Moreover, the country road infrastructure has a very interesting property: all cycles of the country that are made of distinct roads (but not necessarily distinct cities) have an odd length.

We define the beauty value of a simple path in the country (i.e., a path that contains distinct cities) as the sum of the beauty values associated to the roads of the path. The president of the country needs your help to find out the answer of the following question: What is the sum of the beauty values of all the simple paths of the country SigSegv of AGM?

The first line of input will contain two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^6$$$, $$$1 \leq M \leq 10^6$$$), representing the number of cities and the number of bidirectional roads, respectively.

The next $$$M$$$ lines will each contain three integers $$$X$$$, $$$Y$$$, $$$B$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$X \neq Y$$$, $$$1 \leq B \leq 10^9$$$), representing that there is a bidirectional road between the cities $$$X$$$ and $$$Y$$$ with the associated beauty value $$$B$$$. It is guaranteed that the obtained graph is connected and that there are no self loops or multiple edges.

The output must contain one integer value that is equal to the sum of the beauty values of all the simple paths of the country SigSegv of AGM, modulo $$$998244353$$$.

3 3
1 2 1
2 3 2
1 3 3

18

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

1352