Background

In a certain local area network, there are $n$ computers. Due to negligence when setting up the LAN, the connections now form cycles. We know that if a LAN contains cycles, data will keep circulating within the cycle, causing network lag. Because the network cables connecting computers are different, some connections are not very smooth. We use $f(i,j)$ to denote the smoothness between $i$ and $j$; a smaller value of $f(i,j)$ means a smoother connection between $i$ and $j$, and $f(i,j) = 0$ means there is no cable between $i$ and $j$.

Problem 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