Sweet Potatoes for Breakfast

Junpyo has gained a lot of weight. His body fat is 25%, which counts as obese. To eat a balanced diet, Junpyo started eating a sweet potato every morning. After discovering the real taste of sweet potatoes, he decided to grow his own sweet potato field and dig up the best one every morning.

A sweet potato plant has an above-ground part and an underground part, and Junpyo is only interested in the underground part. He calls the graph that abstracts the underground part of a sweet potato a sweet potato graph.

A sweet potato graph is a connected undirected graph that can be divided into five kinds of components. Each edge has an edge strength $c$.

1. Root of the sweet potato graph

   This is the only vertex of the sweet potato graph connected to the above-ground part. This vertex is always vertex 1.

2. Hard roots

   The hard roots form a tree rooted at vertex 1, the root of the sweet potato graph. Any two vertices are connected, and there is exactly one path between them.

3. Tuber (sweet potato)

   This is the edible part of what people usually call a sweet potato. A tuber is connected to one of the ends of the hard roots. If a tuber has $N$ vertices, it is drawn as a convex $N$-gon. In other words, it is a simple cycle.

   The mass of a tuber is the square of the number of vertices in it. For example, if a tuber has 5 vertices, its mass is $5^2=25$.

4. Thin roots

   Thin roots hang from every vertex of a tuber except the vertex connected to the hard roots, and they form a tree.

5. Root tips

   These are the leaf vertices of the sweet potato graph, meaning the ends of the hard roots and the thin roots that have no tuber attached. Root tips grip the soil tightly, so when the plant is pulled out, the root tips must stay underground.

To harvest a sweet potato, Junpyo grabs the "root of the sweet potato graph" and pulls it out of the ground with a very strong force in an instant. When the graph is pulled out, it splits into the "vertices pulled out of the ground" and the "vertices left underground". Every vertex must belong to one of the two parts. Every "vertex pulled out of the ground" is connected to the root, and every "vertex left underground" is connected to some root tip.

To split the graph into two parts, some of its edges must be cut. The sweet potato graph is always cut so that the total strength of the cut edges is minimized. If bad luck strikes, an edge of a tuber may be cut, and this is called a sweet potato being broken. Junpyo is a sweet potato master, so he can pull out the graph so that the mass of the tuber pulled out is maximized. He only handles the best sweet potatoes, so broken sweet potatoes are not counted.

Find the total mass of the sweet potatoes Junpyo harvests by pulling out the sweet potato graph.

The first line contains the number of vertices $N$ and the number of edges $M$ of the sweet potato graph.

The next $M$ lines each contain three integers $u$, $v$, and $c$. Each line describes an edge with strength $c$ that connects vertex $u$ and vertex $v$.

Print the total mass of the sweet potatoes that Junpyo harvests.

$2 \le N \le 1{,}000{,}000$

$N - 1 \le M \le 2{,}000{,}000$

$1 \le u, v \le N$, $u \ne v$

$1 \le c \le 1{,}000{,}000{,}000$

The edges of a tuber never break.