항상 온라인

Wayne은 어느 대도시 통신망의 관리자이다. 이 망은 정점 $n$개와 간선 $m$개를 가진 단순 연결 그래프로 표현된다. 자기 루프가 없고, 두 정점 사이의 간선은 최대 하나이며, 두 정점 사이에는 경로가 적어도 하나 있다. 또한 두 정점 사이에 간선을 공유하지 않는 경로가 최대 두 개 있다.

Wayne은 각 간선의 대역폭을 알고 있지만, 이것만으로는 부족하다. 화면에 보여 줄 통계 자료가 많이 필요하다. 예를 들어 임의의 두 정점 사이에서 전송할 수 있는 최대 데이터 전송률이 얼마인지 알고 싶어 한다. 정점은 1부터 $n$까지 번호가 매겨져 있고, 각 간선이 초당 전송할 수 있는 최대 비트 수가 주어진다. 다음 식의 값을 계산하라.

$\sum_{1 \le s < t \le n}{(s \oplus t \oplus \text{flow}(s, t))}$

여기서 $\oplus$는 비트 단위 배타적 논리합(XOR) 연산자이고, $\text{flow}(s, t)$는 정점 $s$와 정점 $t$ 사이에서 초당 전송할 수 있는 최대 비트 수이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 정수 $n$과 $m$이 주어진다.

이어서 $m$개의 줄에 세 정수 $u$, $v$, $w$가 주어진다. 이는 정점 $u$와 정점 $v$ 사이의 양방향 간선을 뜻하며, 각 방향으로 초당 최대 $w$비트를 전송할 수 있다.

$1 \le T \le 100$, $1 \le n \le 10^5$, $n - 1 \le m \le \frac{3}{2}(n - 1)$, $1 \le u, v \le n$, $u \ne v$, $0 \le w < 10^9$이다.

모든 테스트 케이스의 $n$ 합은 $10^6$을 넘지 않으며, 표준 입력 파일의 크기는 26 MiB를 넘지 않는다.

각 테스트 케이스에 대해 답을 한 줄에 출력한다.

첫 번째 예제에서 $\text{flow}(1, 2) = \text{flow}(1, 3) = 10$이고, $\text{flow}(2, 3) = 11$이다.