관광 벨트

한국에는 관광지가 많다. 그중 하나가 남해안과 서해안에 흩어져 있는 작은 섬들의 무리인 다도해다. 관광 당국은 이 섬들에서 새로운 관광 프로그램을 추진하려 하며, 이를 위해 섬 두 개 이상을 골라 하나의 관광 벨트로 지정한다.

섬은 모두 $n$개다. 여러 섬을 함께 고르면 시너지 효과가 생긴다. 두 섬 $u$와 $v$ 사이의 시너지 효과 $SE(u, v) = SE(v, u)$는 두 섬이 같은 관광 벨트에 포함될 때 기대되는 가치를 나타내는 양의 정수다. 당국은 경제적 이득이 가장 커지도록 섬 두 개 이상을 고르려 한다.

정확히 정의하자. 연결 그래프 $G = (V, E)$를 생각한다. $V$는 정점 $n$개의 집합이고, $E$는 간선 $m$개의 집합이다. 각 정점은 섬 하나를 뜻하며, 서로 다른 두 섬 $u$, $v$ 사이에 시너지 효과 $SE(u, v)$가 정의되어 있으면 간선 $(u, v)$가 존재한다. 정점을 두 개 이상 담은 부분집합을 $A$라 하자. 간선 $(u, v)$의 두 끝점이 모두 $A$에 있으면 그 간선을 $A$의 내부 간선이라 하고, 두 끝점 중 정확히 하나만 $A$에 있으면 $A$의 경계 간선이라 한다.

$2 \le |B| \le n$이며 $G$에서 연결 부분그래프를 이루는 정점 집합 $B$에 대해, $B$의 모든 내부 간선의 시너지 효과가 $B$의 모든 경계 간선의 시너지 효과보다 항상 크면 그 $B$를 관광 벨트 후보라 부른다. 경계 간선이 하나도 없으므로 $V$ 자신은 언제나 후보임에 유의하라.

예를 들어 아래 첫 번째 그래프에는 후보가 $\{1,2\}$, $\{3,4\}$, $\{1,2,3,4\}$ 세 개 있다. $\{2,3,4\}$는 어떤 내부 간선이 어떤 경계 간선보다 크지 않으므로 후보가 아니다. 두 번째 그래프에는 후보가 $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, $\{7,8\}$, $\{3,4,5,6\}$, $\{1,2,3,4,5,6,7,8\}$ 여섯 개 있다. $\{1,2,7,8\}$은 $\{1,2\}$와 $\{7,8\}$을 잇는 간선이 없어 연결되지 않으므로 후보가 아니다.

당국은 $G$의 모든 후보를 살펴보려 한다. 모든 후보의 크기를 더한 값을 출력하는 프로그램을 작성하라. 위 첫 번째 그래프에서는 그 합이 $2 + 2 + 4 = 8$이고, 두 번째 그래프에서는 $2 + 2 + 2 + 2 + 4 + 8 = 20$이다.

입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 5000$, $1 \le m \le n(n-1)/2$). $n$은 연결 그래프 $G$의 섬(정점) 수, $m$은 간선 수다. 섬은 $1$번부터 $n$번까지 번호가 매겨진다. 이어지는 $m$개의 줄에는 각각 세 정수 $u$, $v$, $k$가 주어지며 ($1 \le u \ne v \le n$, $1 \le k \le 10^5$), 이는 $SE(u, v) = k$를 뜻한다. 모든 섬 쌍은 많아야 한 번 나타나고, 그래프는 연결되어 있다.

각 테스트 케이스마다 모든 후보의 크기의 합을 한 줄에 출력한다.