시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 4 4 100.000%

문제

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 国に寄贈される.

どの子供も,父に似て貪欲であるため,相続する鉄道の年間収益の合計ができるだけ大きくなるように 自分の相続分を選ぶ.どの子供についても,年間収益の合計が最大となるような相続分の選び方は,ただ 一通りであることが証明できる.それぞれの鉄道が誰に相続されるかを求めよ.

IOI 国の鉄道の情報と,JOI 氏の子供の人数が与えられたとき,それぞれの鉄道が誰に相続されるかを求 めるプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には,3 個の整数 N, M, K が空白を区切りとして書かれている.これは IOI 国には N 個の都市 と M 本の鉄道があり,JOI 氏には K 人の子供がいることを表す.
  • 続く M 行のうちの i 行目 (1 ≦ i ≦ M) には,整数 Ai, Bi, Ci が空白を区切りとして書かれている.こ れは鉄道 i は都市 Ai と都市 Bi を双方向に結び,年間収益が 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).

예제 입력 1

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

예제 출력 1

1
0
2
1
2
  • 子供 1 は,鉄道 1, 2, 3, 4, 5 のうちから鉄道 1, 4 を選んで相続する.このとき相続する鉄道の年間収益 の合計が 3 + 6 = 9 円となり,これが最大値である.
  • 子供 2 は,残った鉄道 2, 3, 5 のうちから鉄道 3, 5 を選んで相続する.このとき相続する鉄道の年間収 益の合計が 4 + 2 = 6 円となり,これが最大値である.
  • 残った鉄道 2 は IOI 国に寄贈される.

예제 입력 2

3 6 5
1 2 1
1 2 2
2 3 3
2 3 4
3 1 5
3 1 6

예제 출력 2

4
3
2
1
2
1
  • 相続する鉄道の本数は子供によって異なっているかもしれない. 1 本も鉄道を相続しない子供がいるか もしれない.