Sports Days 2.0

시간 제한3초메모리 제한512 MB

요약

가중치가 있는 방향 다중 그래프에서 임의의 정점에서 출발해 총 점수가 K 이상이 되는 최소 간선 수의 경로를 찾고, 간선 수가 100 이하이면 정점 순서를 출력합니다.

문제

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

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

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

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

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

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

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

V E K
v11 v12 c1
...
vi1 vi2 ci
...
vE1 vE2 cE

ここで、

である。

出力は2行からなる。

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

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

예제 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

예제 3

입력

예상 출력