/ 
実行時間制限: 1 sec / メモリ制限: 256 MB
問題文
output checker に不備が見つかったので修正します。修正が終わり次第 rejudge をかけます！！！！！ゴメンナサイ！！！！！！！
rejudge 終了しました許してください何でもしますから
私はちょうど他流試合でもする人のように K を注意して見ていたのです。私は、私の眼、私の心、私の身体、すべて私という名の付くものを五分の隙間もないように用意して、 K に向ったのです。罪のない K は穴だらけというよりむしろ明け放しと評するのが適当なくらいに無用心でした。私は彼自身の手から、彼の保管している要塞の地図を受け取って、彼の眼の前でゆっくりそれを眺める事ができたも同じでした。
K が理想と現実の間に彷徨してふらふらしているのを発見した私は、ただ一打で彼を倒す事ができるだろうという点にばかり眼を着けました。そうしてすぐ彼の虚に付け込んだのです。私は彼に向って急に厳粛な改まった態度を示し出しました。無論策略からですが、その態度に相応するくらいな緊張した気分もあったのですから、自分に滑稽だの羞恥だのを感ずる余裕はありませんでした。私はまず「精神的に向上心のないものは馬鹿だ」といい放ちました。これは二人で房州を旅行している際、 K が私に向って使った言葉です。私は彼の使った通りを、彼と同じような口調で、再び彼に投げ返したのです。しかし決して復讐ではありません。私は復讐以上に残酷な意味をもっていたという事を自白します。私はその一言で K の前に横たわる恋の行手を塞ごうとしたのです。
K は真宗寺に生れた男でした。しかし彼の傾向は中学時代から決して生家の宗旨に近いものではなかったのです。教義上の区別をよく知らない私が、こんな事をいう資格に乏しいのは承知していますが、私はただ男女に関係した点についてのみ、そう認めていたのです。 K は昔から精進という言葉が好きでした。私はその言葉の中に、禁欲という意味も籠っているのだろうと解釈していました。しかし後で実際を聞いて見ると、それよりもまだ厳重な意味が含まれているので、私は驚きました。道のためにはすべてを犠牲にすべきものだというのが彼の第一信条なのですから、摂欲や禁欲は無論、たとい欲を離れた恋そのものでも道の妨害になるのです。 K が自活生活をしている時分に、私はよく彼から彼の主張を聞かされたのでした。その頃からお嬢さんを思っていた私は、勢いどうしても彼に反対しなければならなかったのです。私が反対すると、彼はいつでも気の毒そうな顔をしました。そこには同情よりも侮蔑の方が余計に現われていました。
こういう過去を二人の間に通り抜けて来ているのですから、精神的に向上心のないものは馬鹿だという言葉は、 K に取って痛いに違いなかったのです。しかし前にもいった通り、私はこの一言で、彼が折角積み上げた過去を蹴散らしたつもりではありません。かえってそれを今まで通り積み重ねて行かせようとしたのです。それが道に達しようが、天に届こうが、私は構いません。私はただ K が急に生活の方向を転換して、私の利害と衝突するのを恐れたのです。要するに私の言葉は単なる利己心の発現でした。
「精神的に向上心のないものは、馬鹿だ」
私は二度同じ言葉を繰り返しました。そうして、その言葉が K の上にどう影響するかを見詰めていました。
「馬鹿だ」とやがて K が答えました。「僕は馬鹿だ」
K はぴたりとそこへ立ち留まったまま動きません。彼は地面の上を見詰めています。私は思わずぎょっとしました。私には K がその刹那に居直り強盗のごとく感ぜられたのです。しかしそれにしては彼の声がいかにも力に乏しいという事に気が付きました。私は彼の眼遣いを参考にしたかったのですが、彼は最後まで私の顔を見ないのです。そうして、徐々とまた歩き出しました。
(夏目漱石『こころ』より引用, 強調は JAPLJ による)
精進という言葉を好み，道を何よりも大事にする K ……
うわぁ……，これは K-最短路ですね．間違いない．なんだこれは……．たまげたなあ．
課題
2 つの整数 K, L が与えられる．50 頂点以下の重み付き単純無向グラフであって，ある 2 点間を結ぶ経路のうち K 番目に短いものの長さがちょうど L となるようなものを 1 つ求めよ．
より詳細に，N 頂点の重み付き単純無向グラフを考える．このグラフの辺は異なる2点を結んでいなければならず，ある2点を結ぶような辺は1つしか存在してはいけない(自己ループや多重辺は許されない)．また，それぞれの辺には正の整数の重みがついている必要がある．このグラフの頂点を 1 から N まで番号づけたときに，頂点 1 から頂点 N へ至る経路のうち K 番目に短いものの長さがちょうど L になっていればよい．
経路中では同じ辺を2回以上通ったり，同じ頂点を2回以上訪れたりしても構わない．また，最後だけでなく途中で頂点 N に一回以上訪れるような経路も考える．そのような経路すべてを長さ(これは通る辺の重みの総和である)の昇順に並べたときの K 番目の経路の長さを L にすることが目的である．
入力
K L
これは K 番目に短い経路の長さがちょうど L となるようなグラフを求めることを表す．
出力
N M A_1 B_1 C_1 A_2 B_2 C_2 … A_M B_M C_M
N はグラフの頂点数を，M はグラフの辺数を表す整数である．1 \leq N \leq 50 でなければならない．
続く M 行は各行が 1 つの辺を表す．1 \leq i \leq M に対し A_i, B_i, C_i は，頂点 A_i と頂点 B_i を結ぶ辺が存在し，その重みが C_i であることを表す．1 \leq A_i, B_i \leq N かつ A_i \neq B_i かつ 1 \leq C_i \leq 10^9 でなければならない．
出力されるグラフは単純でなければならず，頂点 1 から頂点 N へ至る K 番目の最短路の長さがちょうど L でなければならない．
ただし，そのようなグラフが 1 つも存在しない場合は -1 とだけ出力せよ．
制限
すべての入力データは以下の制限を満たす．
- 1 \leq K \leq 5000
- 1 \leq L \leq 10^9
採点基準
この問題の入力データは「ふつうのケース」「ちょっときわどいケース」「かなりきわどいケース」の3種類に分けられる．その3種類が具体的にどのようなケースかを明かすことはしない．この問題に対する点数は次のように決まる．
- 「ふつうのケース」にすべて正解すれば 1 点を与える．
- 上に加え「ちょっときわどいケース」にすべて正解すれば，さらに 3 点を与える．
- 上に加え「かなりきわどいケース」にすべて正解すれば，さらに 196 点を与える．
入力例1
3 8
出力例1
3 2 1 2 2 2 3 2
このグラフにおける頂点 1 から頂点 3 へ至る経路を短いものから 3 つ挙げると
- 1 → 2 → 3 と至る長さ 4 の経路
- 1 → 2 → 1 → 2 → 3 と至る長さ 8 の経路
- 1 → 2 → 3 → 2 → 3 と至る長さ 8 の経路
となる．2番目と3番目は長さが同じだが，この問題では長さだけが問題なのでどちらが先に来ても同じことである．また，同じ辺を2回以上通ったり，同じ頂点を2回以上訪れたり，途中で頂点 3 を訪れたりするような経路も考慮することに注意せよ．
入力例2
5000 1
出力例2
-1
statement: 夏目漱石, JAPLJ