Sports Days 2.0

会津大学附属小学校（会津大小）は日本有数の競技プログラマー養成校として有名である。 もちろん、運動会に参加しているときでさえアルゴリズムの修行を欠かせない。 競技プログラミング部部長のあなたはもちろんこの大会でも勝利したい。 今回はある競技に注目する。

ある競技とは会津大小で行われている伝統的な競技だ。 校庭にコーンがV個置いてある。 コーンのいくつかのペアは白線で描かれた矢印で結ばれている。 矢印の先は片側だけについており、整数が併記されている。 同じコーンのペアがの複数の矢印に結ばれている場合もある。

競技者は任意にコーンを選び、移動開始する。 移動は競技者がいるコーンから矢印の上をその向きに移動し、次のコーンへ移る。 同じコーン、同じ矢印を何度も辿っても良い。 競技者はコーンからコーンへの移動後、さらに移動するか移動を終了をするかを選択することができる。

この競技の目的は矢印を辿ることにより、スコアをK以上にすることである。 スコアは矢印を辿る度に併記された整数値が加算されていく。 より少ない経由する矢印の本数でスコアをK以上にした競技者が勝利となる。 矢印が同じ本数の場合はより高いスコアの競技者が勝利となる。

このルールで最適な動きを競技者が行った場合、何本の矢印を経由すべきか出力せよ。 また、経由した矢印の数が100本以下の場合、経由すべきコーンを順にすべて出力せよ。 最適な動きが複数存在する場合があるが、どの動きの結果を出力しても良い。 スコアをK以上にする動きが存在しない場合は-1を出力せよ。

また、コーンにはすべて0からV-1までの番号が振られており、 色はすべて緑色（意味深）である。

Input

入力は以下の形式で与えられる。

V E K
v₁₁ v₁₂ c₁
...
v_i1 v_i2 c_i
...
v_E1 v_E2 c_E

ここで、

• Vはコーンの数
• Eは矢印の数
• v_i,1は矢印iの始点のコーン番号
• v_i2は矢印iの終点のコーン番号
• c_iは矢印に併記されている整数

である。

Constraints

入力は以下の条件を満たす。

• 入力はすべて整数
• 2≤V≤150
• 0≤E≤V×V
• 0<K≤10⁶
• 0≤ v_i1, v_i2 < V (0<i≤E)
• v_i1 ≠ v_i2 (0<i≤E)
• 0<c_i ≤ 100 (0<i≤E)
• v_i1 = v_j1 かつ v_i2 = v_j2 (i ≠ j, 0<i,j≤E)となるようなi, jが含まれる入力も存在する。

Output

出力は2行からなる。

• 1行目　最適な動きを行った場合の経由する矢印の本数で出力
• 2行目　経由すべきコーンの番号を経由する順番に空白区切りで出力

最適な動きが複数存在する場合があるが、どの動きの結果を出力しても良い。 経由すべき矢印の本数が100本を越える場合、2行目は出力してはいけない。 スコアをK以上にする最適な動きが存在しない場合は-1を1行目に出力し、 2行目に何も出力してはいけない。

Sample Input 1

3 9 89
2 0 2
1 0 3
2 0 1
2 0 3
0 1 1
0 1 2
1 2 3
0 1 1
1 0 2

Output for the Sample Input 1

34
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0

Sample Input 2

2 0 1

Output for the Sample Input 2

-1

Sample Input 3

7 8 4000
0 1 1
1 0 1
1 2 2
2 3 2
3 4 2
5 4 3
3 5 4
5 6 5

Output for the Sample Input 3

3991