[KOITP] 군사 도로망(Not Solved)

출    처 : http://koitp.org/problem/MILITARY_ROAD_NETWORK/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	256 MB	39	4 (10%)	2

문제

어떤 나라는 $N$개의 도시로 구성되어 있다. 도시들을 연결하는 도로들이 있는데, 도로라는 것은 서로 다른 두 도시를 연결하는 기능을 하며, 양방향 통행이 가능하고 하나의 도시 쌍에 대해서는 최대 하나의 도로만이 존재 가능한 것으로 가정한다. 이 나라는 몇 년간 전쟁을 치르고 있어서 많은 도로가 파괴된 상태이다. 이제 도로들을 정비하여 모든 쌍의 도시가 단 하나의 길(길은 이어서 갈수 있는 도로들을 말함)로 연결되도록 하고 싶다. 군사적인 이유로, 두 도시를 연결하는 길이 두 가지 이상 존재하는 것을 원하지 않기 때문이다. 모든 쌍의 도시 사이에 도로를 만들 수 있는 것은 아니라서, 한 쌍의 도시가 있는 경우 이들 사이에는 이미 도로가 존재, 도로를 만드는 것이 가능, 도로를 만드는 것이 불가능한 세가지 경우가 존재할 수 있다. 도로 정비 과정에서 존재하는 도로를 제거해야 하는 경우도 있음에 주의하라. 각 도로는 만들거나 제거할 때는 비용이 발생하며 비용은 도로마다 다를 수 있다. (이 나라는 가상의 세계에 존재하는 것이므로 서로 다른 두 도로가 교차하는 문제는 전혀 고려할 필요가 없다.)

위의 그림에 하나의 예가 제시되어 있다. 왼쪽이 초기 상태인데, 이 나라는 $5$개의 도시로 구성되어 있으며, $3$개의 실선으로 표시된 도로는 기존에 존재하는 것이며, $3$개의 점선으로 표시된 도로는 건설이 가능한 것이다. 문제의 조건을 만족하면서 최소의 비용을 지불하는 방법은 도시 $1$과 $2$ 사이의 도로를 제거하고 (비용 $1$) 도시 $3$과 $5$ 사이와 도시 $4$와 $5$ 사이의 도로를 건설하여 (비용 $6$), 오른쪽 그림과 같은 상태를 만드는 것이다. 총 비용은 $7$이 된다. 이 예에서 모든 경우들을 따져 보면 정답은 유일함을 알 수 있다.

도시의 수, 지금 존재하는 $M$개의 도로들과 각 도로를 제거하는 비용, 도로를 건설하는 것이 가능한 $K$개의 도시의 쌍과 각 도로의 건설 비용을 받아서 위의 목적을 달성하는 비용의 최소값과 그 최소값을 달성하는 방법이 유일한 지를 확인하는 프로그램을 작성하라.

입력

첫 줄에 자연수 세 개가 주어지는데, 첫 수는 $N(1\le N\le 100,000)$, 둘째 수는 $M(0\le M\le 300,000)$, 셋째 수는 $K(0\le K\le 300,000)$이다. $M$이나 $K$가 $0$일 수도 있음에 주의하라. 하지만, 둘 다 $0$인 경우는 없다. 도시들은 $1$ 부터 $N$까지 번호가 붙은 것이다.

이후 $M$개의 줄에 기존에 존재하는 각 도로에 대해서 양쪽 끝 도시의 번호와 도로를 제거하는 비용이 $3$개의 자연수로 주어진다.

이후 $K$개의 줄에 건설이 가능한 도로들에 대해서 양쪽 끝 도시의 번호와 건설하는 비용이 주어진다.

모든 비용 값은 ${10}^9$ 보다 크지 않은 자연수이며, 항상 목적을 달성할 수 있도록 입력이 주어진다.

출력

첫 줄에 최소 비용의 값을 자연수로 출력한다. 다시 한 칸을 떼고 최소비용을 만든 방법이 유일한 경우 "unique", 그렇지 않은 경우 "not unique"를 따옴표 제외하고 출력한다.

힌트

입력 예제 1

5 3 3
1 2 1
1 3 4
2 3 2
3 5 2
3 4 7
4 5 4

출력 예제 1

7 unique

입력 예제 2

3 3 0
1 2 3
1 3 3
2 3 3

출력 예제 2

3 not unique