만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

벤자민 고무나무

시간 제한3초메모리 제한512 MB

요약
연결된 가중 무방향 그래프의 정점을 공집합이 아닌 두 그룹으로 나눌 때, 두 그룹을 잇는 간선의 가중치 합이 최소가 되도록 한다.
난이도

어려움10점 중 8점

유형
그래프, 최소 신장 트리, 그리디, 분할 정복
정답자
아직 제출이 없습니다

문제

뒷마당에 벤자민 고무나무가 한 그루 있다. 이 나무의 뿌리는 집 밑을 파고들지 않고 마당의 빈 공간으로만 뻗어서, 친구들은 이 나무를 착한 벤자민이라고 부른다. 새로 집을 짓는 친구가 같은 나무를 갖고 싶어 해서, 뿌리 일부를 잘라 나눠 주기로 했다.

나무의 뿌리는 NN개이고 11번부터 NN번까지 번호가 붙어 있다. 서로 다른 두 뿌리를 잇는 연결이 MM개 있고, 뿌리 aa와 bb를 잇는 연결을 끊는 데는 힘 ww가 든다.

뿌리 전체를 비어 있지 않은 두 무리로 나누려고 한다. 두 무리 사이를 잇는 연결은 하나도 남으면 안 되고, 드는 힘은 끊은 연결의 힘을 모두 더한 값이다. 필요한 힘의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다 (1≤T≤201 \le T \le 20).

각 테스트 케이스의 첫 줄에는 뿌리의 개수 NN과 연결의 개수 MM이 주어진다 (2≤N≤5002 \le N \le 500, N−1≤M≤N(N−1)/2N-1 \le M \le N(N-1)/2).

다음 MM개 줄에는 세 정수 aia_i, bib_i, wiw_i가 주어진다 (1≤ai,bi≤N1 \le a_i, b_i \le N, ai≠bia_i \ne b_i, 1≤wi≤10001 \le w_i \le 1000). 뿌리 aia_i와 bib_i가 연결되어 있고, 그 연결을 끊는 데 힘 wiw_i가 든다는 뜻이다.

두 뿌리를 잇는 연결은 많아야 하나이고, 모든 뿌리는 연결을 따라가면 서로 이어진다.

출력

각 테스트 케이스마다 필요한 힘의 최솟값을 한 줄에 하나씩 출력한다.

힌트

첫 번째 예제에서 뿌리 11만 떼어 내면 2+3+5=102+3+5=10의 힘이 든다. 대신 {1,2}\{1,2\}와 {3,4}\{3,4\}로 나누면 3+5+5+5=183+5+5+5=18의 힘이 든다.

예제7

  1. 예제 1

    입력
    1
4 6
1 2 2
1 3 3
1 4 5
2 3 5
2 4 5
3 4 8
    예상 출력
    10

  2. 예제 2

    입력
    1
2 1
1 2 1000
    예상 출력
    1000

  3. 예제 3

    입력
    1
5 4
1 2 4
2 3 1
3 4 7
4 5 3
    예상 출력
    1

  4. 예제 4

    입력
    1
6 6
1 2 3
2 3 1
3 4 4
4 5 1
5 6 5
6 1 9
    예상 출력
    2

  5. 예제 5

    입력
    1
10 22
1 2 100
1 3 100
1 4 100
1 5 100
2 3 100
2 4 100
2 5 100
3 4 100
3 5 100
4 5 100
6 7 100
6 8 100
6 9 100
6 10 100
7 8 100
7 9 100
7 10 100
8 9 100
8 10 100
9 10 100
3 6 2
5 10 3
    예상 출력
    5

  6. 예제 6

    입력
    1
6 15
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1
    예상 출력
    5

  7. 예제 7

    입력
    4
2 1
1 2 7
3 3
1 2 5
2 3 5
1 3 5
4 4
1 2 1
2 3 1
3 4 1
4 1 1
5 6
1 2 10
1 3 10
2 3 10
3 4 1
4 5 6
3 5 6
    예상 출력
    7
10
2
7