Hamako Online Judge

TLE
1sec

MLE
256MB

得点
100

問題

　IOI 国の鉄道をすべて所有していた大富豪の JOI 氏が逝去した．鉄道は遺言に従って分割相続されることになった．
　IOI 国には N 個の都市と，それらの間を結ぶ M 本の鉄道がある．都市には 1 から N までの番号が付けられ，鉄道には 1 から M までの番号が付けられている．鉄道 i は都市 A_i と都市 B_i の間を双方向に結び，また年間に C_i 円の収益を上げている．鉄道の利用客数や乗車料金は多様なため，C₁, ..., C_M はそれぞれ相異なる．同じ二つの都市を結ぶ鉄道が複数あるかもしれない．
　遺言には以下のように鉄道の分割相続の方法が記されていた．

鉄道は，JOI 氏の K 人の子供に相続させる．子供たちには年齢が高い順に 1 から K までの番号が付いている．
それぞれの子供は，M 本の鉄道のうちのいくつか (0 本の場合もありうる) を相続する．
はじめに M 本の鉄道の中から，子供 1 がいくつか選び，自分の相続分とする．次に残った鉄道の中から，子供 2 が自分の相続分を決める．以下同様にして，K 人の子供が順番に，自分の相続分を決めていく．
どの子供も，すでに相続先が決まった鉄道は相続することができない．すなわち，子供 j の相続分の中に鉄道 i が含まれていたら，それより若い子供 k (k > j) は鉄道 i を自分の相続分の中に含めることができない．
どの子供も，自分の相続分を決める際，相続分がサイクルを含まないようにしなければならない．すなわち，鉄道 i₁, i₂, ..., i_m (i₁, i₂, ..., i_m は相異なる) を一回ずつ利用することである都市から出発して同じ都市に戻ってくることができるとき，どの子供も，鉄道 i₁, i₂, ..., i_m をすべて一人で相続することはできない．
誰にも相続されずに残った鉄道は IOI 国に寄贈される．

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

課題

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

入力

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

1 行目には，3 個の整数 N, M, K が空白を区切りとして書かれている．これは IOI 国には N 個の都市と M 本の鉄道があり，JOI 氏には K 人の子供がいることを表す．
続く M 行のうちの i 行目 (1 ≤ i ≤ M) には，整数 A_i, B_i, C_i が空白を区切りとして書かれている．これは鉄道 i は都市 A_i と都市 B_i を双方向に結び，年間収益が C_i 円であることを表す．

出力

　出力は M 行からなる．i 行目 (1 ≤ i ≤ M) には，鉄道 i を相続する子供の番号を出力せよ．IOI 国に寄贈される場合は 0 と出力せよ．

制限

　すべての入力データは以下の条件を満たす．

2 ≤ N ≤ 1 000．
1 ≤ M ≤ 300 000．
1 ≤ K ≤ 10 000．
1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N (1 ≤ i ≤ M)．
A_i ≠ B_i (1 ≤ i ≤ M)．
1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ M)．
C_i ≠ C_j (1 ≤ i < j ≤ M)．

小課題

小課題 1 [15 点]

K ≤ 10 を満たす．

小課題 2 [85 点]

　追加の制約はない．

入出力例

入力例 1

出力例 1

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

入力例 2

出力例 2

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

002 - 遺産相続 (Inheritance)

問題

課題

入力

出力

制限