상속

IOI국의 모든 철도를 소유하고 있던 대부호 JOI가 세상을 떠났다. 철도는 유언에 따라 분할 상속되기로 했다.

IOI국에는 N개의 도시와 그 사이를 잇는 M개의 철도가 있다. 도시에는 1부터 N까지 번호가 붙어 있고, 철도에는 1부터 M까지 번호가 붙어 있다. 철도 i는 도시 Ai와 도시 Bi를 양방향으로 잇고, 1년에 Ci엔의 수익을 낸다. 철도의 이용객 수와 운임이 다양하기 때문에 C1, ..., CM은 서로 다르다. 같은 두 도시를 잇는 철도가 여러 개 있을 수도 있다.

유언에는 철도를 분할 상속하는 방법이 다음과 같이 적혀 있었다.

• 철도는 JOI의 K명의 자식이 상속받는다. 자식들에게는 나이가 많은 순서대로 1부터 K까지 번호가 붙어 있다.
• 각 자식은 M개의 철도 중 몇 개(0개일 수도 있다)를 상속받는다.
• 먼저 M개의 철도 중에서 자식 1이 몇 개를 골라 자신의 상속분으로 한다. 다음으로 남은 철도 중에서 자식 2가 자신의 상속분을 정한다. 이하 마찬가지로 K명의 자식이 순서대로 자신의 상속분을 정해 나간다.
• 어떤 자식도 이미 상속 대상이 정해진 철도를 상속받을 수 없다. 즉, 자식 j의 상속분에 철도 i가 들어 있다면, 그보다 어린 자식 k(k > j)는 철도 i를 자신의 상속분에 넣을 수 없다.
• 어떤 자식도 자신의 상속분을 정할 때 상속분이 사이클을 포함하지 않도록 해야 한다. 즉, 철도 i1, i2, ..., im(i1, i2, ..., im은 서로 다르다)을 한 번씩 이용해 어떤 도시에서 출발해 같은 도시로 돌아올 수 있을 때, 어떤 자식도 철도 i1, i2, ..., im을 모두 혼자 상속받을 수 없다.
• 아무도 상속받지 않고 남은 철도는 IOI국에 기증된다.

모든 자식은 아버지를 닮아 탐욕스럽기 때문에 상속받는 철도의 1년 수익 합계가 가능한 한 커지도록 자신의 상속분을 고른다. 어떤 자식에 대해서도 1년 수익 합계가 최대가 되는 상속분 선택 방법은 하나뿐임이 증명된다. 각 철도가 누구에게 상속되는지 구하라.

IOI국의 철도 정보와 JOI의 자식 수가 주어졌을 때, 각 철도가 누구에게 상속되는지 구하는 프로그램을 작성하라.

표준 입력에서 다음 입력을 읽는다.

• 첫째 줄에는 세 정수 N, M, K가 공백을 구분으로 쓰여 있다. 이는 IOI국에 N개의 도시와 M개의 철도가 있고, JOI에게 K명의 자식이 있음을 나타낸다.
• 이어지는 M개의 줄 중 i번째 줄(1 ≤ i ≤ M)에는 정수 Ai, Bi, Ci가 공백을 구분으로 쓰여 있다. 이는 철도 i가 도시 Ai와 도시 Bi를 양방향으로 잇고 1년 수익이 Ci엔임을 나타낸다.

출력은 M개의 줄로 이루어진다. i번째 줄(1 ≤ i ≤ M)에는 철도 i를 상속받는 자식의 번호를 출력하라. IOI국에 기증되는 경우에는 0을 출력하라.

• 2 ≤ N ≤ 1 000.
• 1 ≤ M ≤ 300 000.
• 1 ≤ K ≤ 10 000.
• 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N (1 ≤ i ≤ M).
• Ai ≠ Bi (1 ≤ i ≤ M).
• 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).
• Ci ≠ Cj (1 ≤ i < j ≤ M).