P2820 Local Area Network

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$.

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.

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$.

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

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