cho.sh개구리 유포자
정해진 순서로 통신 채널이 하나씩 끊길 때, 매 공격 직전에 남아 있는 그래프의 최소 신장 숲 가중치를 구하고 연결되지 않으면 FAIL을 출력한다.
보통6유니온 파인드그래프최소 신장 트리정렬아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제
특수부대 알파 X에 임무가 하나 떨어졌다. 앞으로 3개월에서 6개월 안에 나라 안의 개구리와 개구리 유포자를 모두 없애는 것이다. 개구리는 사람 사이의 통신 회선을 공격하기 때문에 위험하다. 개구리가 회선을 한 번 공격하면 그 회선은 끊어져서 다시는 쓸 수 없다.
부대원은 N명이고, 부대원 사이에는 통신 회선이 C개 있다. 두 부대원은 직접 이어진 회선이나 다른 부대원을 거치는 경로로 살아 있는 회선이 연결되어 있을 때만 서로 메시지를 주고받는다.
같은 두 사람 사이에 회선이 여러 개 있을 수도 있다. 그런데 회선으로 통신하는 데에는 위험이 따른다. 해커를 막기에 충분히 안전하지 않을 수도 있고, 물리적으로 손상되어 통신을 망칠 수도 있다. 이 위험은 위험 지수(RI)로 나타내며, 회선마다 RI 값이 정해져 있다.
가끔은 부대 전체에 전해야 하는 중요한 메시지가 생긴다. 메시지는 한 부대원에게서 출발해 다른 몇몇 부대원에게 전달되고, 메시지를 받은 부대원이 다시 다른 부대원에게 전달하는 식으로 퍼진다. 더 안전한 경로로 이미 닿는 사람에게는 메시지를 보내지 않아도 된다. 다만 마지막에는 모든 부대원이 메시지를 받아야 한다. 이렇게 단체 메시지를 한 번 보낼 때의 총 위험 지수(TRI)는 메시지를 나르는 데 쓴 회선의 RI를 모두 더한 값이다.
부대는 단체 메시지를 보낼 때마다 TRI를 최소로 하고 싶어 하며, 그 최솟값을 LTRI라고 부른다. LTRI는 메시지를 처음 보내는 사람이 누구인지와 상관없이 같다. 정보반은 개구리가 회선을 공격하는 순서를 이미 알아냈다.
공격이 일어나기 직전마다 그때까지 살아 있는 회선만으로 계산한 LTRI를 구하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 부대원 수 N과 처음에 살아 있는 회선 수 C가 주어진다.
이어지는 C개의 줄에는 회선 정보가 개구리가 공격하는 순서대로 주어진다. 그중 i번째 줄에는 세 정수 a, b, r이 주어지며, 부대원 a와 부대원 b를 잇는 회선의 위험 지수가 r이라는 뜻이다. a와 b는 같을 수도 있다.
제한
- 1≤N≤100
- 1≤C≤105
- 1≤T≤1000이고, 모든 테스트 케이스의 C를 더한 값은 2×105 이하이다
- 1≤a,b≤N
- 1≤r≤109
출력
각 테스트 케이스마다 먼저 Case #X: 형식의 줄을 출력한다. X는 1부터 시작하는 테스트 케이스 번호이다.
그 다음 C개의 줄을 출력한다. 그중 i번째 줄에는 입력의 i번째 회선이 공격당하기 직전의 LTRI를 출력한다. 그 시점에는 앞의 i−1개 회선이 이미 끊어졌고 i번째부터 C번째까지의 회선이 살아 있다. 단체 메시지가 모든 부대원에게 닿을 수 없으면 그 줄에는 대신 FAIL을 출력한다.