Description

Now we need to resolve the cycle problem. We will remove some cables so that the network contains no cycles, without changing the connectivity of the original graph's nodes, and the sum of $f(i,j)$ over the removed cables is maximized. Please compute this maximum value.

Input Format

The first line contains two positive integers $n, k$. The next $k$ lines each contain three positive integers $i, j, m$, indicating that there is a cable between computers $i$ and $j$ with smoothness $m$.

Output Format

A single positive integer: the maximum value of $\sum f(i,j)$.

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

8

Hint

Constraints: For all testdata, it is guaranteed that $1 \le n \le 100$, $1 \le f(i,j) \le 1000$.

Translated by ChatGPT 5