문제
IOI 나라의 철도를 모두 소유했던 대부호 JOI씨가 서거했다. 철도는 유언대로 분할상속 될 것이다.
IOI 나라에는 N개의 도시가 있고, 그들을 잇는 M개의 철도가 있다. 도시에는 1부터 N까지의 번호가 붙어있고, 철도에는 1부터 M까지의 번호가 붙어있다. 철도 i는 도시 Ai와 Bi의 사이를 쌍방향으로 잇고, 매년 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 나라에 기증한다.
어떤 자손도, 아버지처럼 금전욕이 많기 때문에, 상속받는 철도의 연간수익의 합계가 최대가 되게 상속분을 결정한다. 어떤 자손에 대해서도, 연간수익의 합계가 최대가 되는 상속분의 선택 방식은, 한 가지 방법임을 증명 할 수 있다. 각각의 철도가 누구에게 상속되는지를 구하여라.
입력
첫째 줄에는 세 개의 정수 N, M, K가 공백으로 구분되어 입력된다. 이것은 IOI나라에는 N개의 도시와 M개의 철도가 있고, JOI씨는 K명의 자손이 있다는 것을 의미한다.
그 후 M개의 줄의 i번째 줄에는 (1≤i≤M) 정수 Ai, Bi, Ci가 공백으로 구분되어 입력된다. 이것은 철도 i가 Ai와 Bi를 양방향으로 잇고, 연간소득이 Ci라는 것을 의미한다.
* 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)
출력
i번째 줄에 (1≤i≤M), 철도 i를 상속받는 자손의 번호를 출력한다. IOI 나라에 기증될 경우는 0을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | K ≤ 10 |
| #2 | 85점 | 추가 제약조건이 없다. |
예제 #1
3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2
1
0
2
1
2
예제 #2
3 6 5
1 2 1
1 2 2
2 3 3
2 3 4
3 1 5
3 1 6
4
3
2
1
2
1
로그인해야 코드를 작성할 수 있어요.