17726번 - Inheritance 서브태스크다국어

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)．