Morning Sweet Potato

Junpyo has gained a lot of weight. His body fat is 25%, which is obese. To eat a balanced diet, Junpyo started eating a sweet potato every morning. After he came to appreciate the true taste of sweet potatoes, he decided to farm them himself and dig up the best sweet potato every morning.

A sweet potato plant is divided into an aboveground part and an underground part, and Junpyo cares only about the underground part. Junpyo calls the abstract graph of the underground part 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 a strength $c$.

1. Root of the sweet potato graph

The root is the single vertex that connects to the aboveground part. It is always vertex 1.

2. Hard roots

The hard roots form a tree rooted at vertex 1 of the sweet potato graph. Any two vertices are connected by exactly one path.

3. Tuber (sweet potato)

The tuber is the edible part of a sweet potato. Each tuber is attached 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, a tuber is a simple cycle.

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

4. Thin roots

Thin roots hang from every vertex of a tuber except the vertex that connects to the hard roots. They form a tree.

5. Root tips

Root tips are the leaves of the sweet potato graph. They are the ends of the hard roots that have no tuber attached, and the ends of the thin roots. Root tips grip the soil tightly, so when the root is pulled out, the tips stay in the ground.

To harvest a sweet potato, Junpyo holds the root of the sweet potato graph and pulls it out of the ground with a single very strong force. Pulling the graph splits its vertices into two groups: the vertices pulled out of the ground and the vertices left in the ground. Every vertex belongs to exactly one group. Every pulled-out vertex is connected to the root, and every vertex left in the ground is connected to some root tip.

To split the graph into two groups, some edges must be cut. A 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. In that case, the sweet potato is said to be broken. Junpyo is a sweet potato master, so he pulls out the graph so that the total mass of the tubers pulled out is maximized. He only handles perfect sweet potatoes, so broken ones are not counted.

Compute the total mass of the sweet potatoes Junpyo harvests by pulling out the 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 describes an edge with strength $c$ that connects vertices $u$ and $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$

An edge of the hard roots or of a tuber is never cut in a way that leaves a sweet potato (a vertex of a tuber) in the ground.