제우스

번개의 신 우제는 Treewidth가 2 이하인 무방향 연결 그래프를 가지고 있다. 임의의 두 정점을 직접 잇는 간선은 최대 하나이며, 모든 간선은 서로 다른 두 정점을 잇는다. 각 간선에는 양의 정수 가중치가 붙어 있다. 그래프의 각 정점은 1 이상 $N$ 이하의 서로 다른 정수로 표현된다.

$dist(i, j)$를 $i$번 정점과 $j$번 정점 사이의 최단 경로 길이라고 하자. 우제가 가진 그래프가 주어질 때 $\sum_{1 \le i < j \le N} dist(i, j)$를 출력하라.

첫 줄에 테스트 케이스의 개수 $T$($1 \le T \le 60$)가 주어진다. 이후 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 수 $N$과 간선의 수 $M$이 주어진다($3 \le N \le 50\,000$, $2 \le M \le 100\,000$). 이후 $M$개의 줄에 세 정수 $u$, $v$, $w$가 주어지며, 이는 정점 $u$와 $v$를 잇는 가중치 $w$의 간선이 존재한다는 뜻이다($1 \le u, v \le N$, $u \ne v$, $0 \le w \le 1\,000$).

모든 테스트 케이스에 대한 $N + M$의 합은 1600000 이하이다.

각 테스트 케이스마다 "Case #C"를 한 줄에 출력한다. 여기서 $C$는 테스트 케이스의 번호이다. 다음 줄에 답을 정수로 출력한다.

연결 그래프 $G$의 트리폭이 2 이하라는 것은, 정점이 하나이고 간선이 없는 그래프에서 다음 세 연산을 적절히 반복해서 $G$와 동형인 그래프를 얻을 수 있다는 것과 같다.

• 연산 1: 이미 존재하는 정점 A와 정점 X를 간선으로 연결한다.
• 연산 2: 이미 존재하며 간선으로 직접 연결된 두 정점 A와 B에 대해, A와 정점 X를 간선으로 연결하고 B와 X를 간선으로 연결한다.
• 연산 3: 연산 2와 같이 A와 X, B와 X를 연결한 뒤, A와 B를 잇는 간선을 제거한다.