How Many to Be Happy?

Let $G$ be a connected simple undirected graph in which every edge has a weight. Recall the minimum spanning tree (MST) problem. For each edge $e$ of $G$, we ask how much $G$ must be modified before $e$ belongs to an MST of $G$. Some MST of $G$ may already contain $e$. In that case we say that $e$ is happy in $G$, and we define $H(e) = 0$. It may also happen that no MST of $G$ contains $e$. In that case we say that $e$ is unhappy in $G$. We may then delete some edges of $G$ to obtain a connected graph $G'$ in which $e$ is happy. $H(e)$ is the minimum number of edges to delete from $G$ so that $e$ is happy in the resulting graph $G'$.

Figure E.1. A complete graph with 3 nodes.

The graph in Figure E.1 has 3 nodes and 3 edges. Its MST consists of the two edges with weights 1 and 2, so those two edges are happy in the graph. To make the edge of weight 3 happy, delete either one of the two happy edges.

Given a connected simple undirected graph $G$, compute $H(e)$ for every edge $e$ of $G$ and print the total sum.

The first line contains two positive integers $n$ and $m$, the number of vertices and the number of edges of the graph, where $n \le 100$ and $m \le 500$. The vertices are numbered from 1 to $n$.

Each of the next $m$ lines contains three positive integers $u$, $v$, and $w$, describing an edge between vertex $u$ and vertex $v$ with weight $w$. Every weight is an integer between 1 and 500, inclusive.

The graph is connected, it has no self loop, and no two edges join the same pair of vertices.

Print one integer $S$, the sum of $H(e)$ over all edges $e$ of $G$.