뉴 아시아 왕국에는 M개의 도로로 연결된 N개의 마을이 있다. 어떤 도로들은 자갈로, 그리고 다른 도로들은 콘크리트로 포장이 되어있다. 무료도로를 유지하기 위해서는 많은 경비가 필요하기 때문에 이 왕국에서 모든 도로를 무료화 하는 것은 불가능하여 보인다. 따라서 새로운 도로유지 방안이 필요하다.

왕은 무료도로의 수를 가능한 한 최소화하되, 어떤 마을에서 다른 마을로 갈 때 반드시 오 직 하나의 무료도로로 이루어 경로가 있도록 결정하였다. 또한 콘크리트 도로가 현대 교통에 적합하지만, 왕은 자갈길을 걷는 것이 매우 흥미 있다고 생각하였다. 결과적으로 왕은 정확히 K개의 자갈도로를 무료도로로 유지하기로 결정하였다.

예를 들어 뉴 아시아 왕국의 마을과 도로는 그림 1a와 같다. 만일 왕이 2개의 자갈도로를 무료로 하고자 하면, 왕국은 그림 1b와 같이 (1, 2), (2, 3), (3, 4), (3, 5)를 무료로 하여야 한다.

이 계획은 왕의 요구사항을 만족하는데 그 이유는 (1) 모든 두 마을이 무료도로를 통하여 연결되어 있으며, (2) 가능한 가장 적은 수의 무료도로를 가지고 있고, (3) 정확히 두 개의 무료 자갈도로를 포함한다: (2, 3)과 (3, 4)

그림1:

(a) 뉴 아시아 왕국의 마을과 도로 예. 실선은 콘크리트 도로를 점선은 자갈도로를 뜻함.

(b) 정확히 두 개의 무료 자갈도로를 포함하는 도로유지방안. 무료도로만 표시되었음. 해야 할 작업

입력

• N, 마을의 개수 (1≤ N ≤20,000), M, 도로의 개수 (1≤ M ≤100,000), 그리고 K, 왕이 무료로 유지하기를 원하는 자갈도로의 개수 (0≤ K ≤ N-1)
• 다음 M 줄에는 1에서부터 M까지의 도로가 기술된다. (i + 1)번째 줄은 도로 i를 뜻한다. 여기 에는 세 개의 정수가 하나의 빈칸을 사이에 두고 주어진다:
  • ui와 vi, 도로 i에 의해 연결되는 두 마을. 마을은 1부터 N으로 표시되며,
  • ci는 도로 i의 종류; ci = 0은 자갈 도로, ci = 1은 콘크리트 도로를 뜻한다.

출력

그렇지 않은 경우, 여러분의 프로그램은 유효한 도로유지방안의 무료도로들을 한 줄에 하나 씩 열거하여 출력하여야 한다. 도로는 입력 시 주어 형태로 출력이 되어야 하나, 도로의 순 서는 어떤 순서라도 무방하다. 만일 유효한 도로유지방안이 여러 개가 있는 경우, 그 중 하나 만 출력하면 된다.

입출력 예

입력

5 7 2 
1 3 0 
4 5 1 
3 2 0 
5 3 1 
4 3 0
1 2 1
4 2 1
(이 입력 예는 그림 1a와 같다)

출력

3 2 0
4 3 0 
1 2 1
5 3 1

(이 출력 예는 그림 1b와 같다)

시간 및 메모리 제한

채점방법

출처: Asia-Pacific Informatics Olympiad 2008