몇 개를 지워야 행복할까

가중치가 붙은 연결 단순 무향 그래프 $G$가 있다. 잘 알려진 최소 신장 트리(MST) 문제를 떠올려 보자. 여기서는 각 간선 $e$에 대해, $e$가 $G$의 MST에 들어가게 하려면 $G$를 얼마나 고쳐야 하는지를 묻는다. $e$를 포함하는 MST가 $G$에 이미 있다면 $e$는 $G$에서 행복하다고 하고, $H(e) = 0$으로 정의한다. $e$를 포함하는 MST가 하나도 없다면 $e$는 $G$에서 불행하다고 한다. 이때 $G$에서 간선을 몇 개 지워 연결 그래프 $G'$을 만들고, 그 안에서 $e$가 행복해지게 할 수 있다. $H(e)$는 이렇게 $e$가 행복해지는 $G'$을 얻으려고 $G$에서 지우는 간선의 최소 개수다.

그림 E.1. 정점이 3개인 완전 그래프.

그림 E.1의 그래프는 정점이 3개, 간선이 3개다. 이 그래프의 MST는 가중치가 1과 2인 간선 두 개로 이루어지므로 그 두 간선은 행복하다. 가중치가 3인 간선을 행복하게 만들려면 행복한 두 간선 중 아무거나 하나만 지우면 된다.

연결 단순 무향 그래프 $G$가 주어지면 모든 간선 $e$의 $H(e)$를 구해 그 총합을 출력한다.

첫째 줄에 그래프의 정점 수 $n$과 간선 수 $m$이 양의 정수로 주어진다. $n \le 100$이고 $m \le 500$이다. 정점에는 1번부터 $n$번까지 번호가 붙어 있다.

다음 $m$개 줄에는 각각 양의 정수 $u$, $v$, $w$가 주어지며, 정점 $u$와 정점 $v$를 잇는 가중치 $w$인 간선을 뜻한다. 가중치는 1 이상 500 이하의 정수다.

주어지는 그래프는 연결되어 있고, 자기 자신을 잇는 간선은 없으며, 같은 정점 쌍을 잇는 간선이 둘 이상 있는 경우도 없다.

첫째 줄에 모든 간선 $e$에 대한 $H(e)$의 합 $S$를 출력한다.