時間制限:4000ミリ秒
メモリ制限:65536KB
問題
「男なら女性を待たせたり、約束を破ったりはしない！」と北京ダックの父は言った。彼の小さなダックの頭をなでながら、彼は物語をはじめた。
「リマーガット王子は彼の国であるUDF王国 - 自由の三角連合 - に住んでいる。ある日、彼らの隣国が彼らのもとに、外交戦略のためにウユー姫を送った。」
「そして、ウユー姫はリマーガットに、もし王子がK番目に短い経路で姫に会いに来たならば、彼を宮殿に招いてUDFと戦略上の話をすることができる、という内容を記した手紙を送った。」
取引とその可愛い娘に興味がでたので、リマーガット王子は本当に夢中になった。彼はあなた、つまり総理大臣の助けを必要としている！
詳細: UDFの首都はN個の駅で構成されている。宮殿はSであり、番号Tの駅は王子の現在地である。M個の一方通行の道が駅どうしを接続している。リマーガットが姫のもとに到達するための道筋は、同じ駅を2度以上通ることが-例えそれがSまたはTであっても-ありうる。同じ長さの別の道筋は別々のものとして扱われる。
入力
入力の最初の行は、数字Nと数字Mが空白を区切りとして書かれている。駅は1からNまでの番号がつけられている。
続くM行には、3つの整数A,B,T(1<=a<=N, 1<=b<=N, 1<=T<=100)が空白を区切りとして書かれている。これはA番目の駅からB番目の駅へ、T時間で到達する道が存在することを意味している。
最後の行は、3つの整数S,T,K(1<=S, T<=N, 1<=K<=1000)が空白を区切りとして書かれている。
出力
ウユー姫を迎えに行くためのK番目に短い道筋のためにかかる時間をあらわす1つの整数を含む1行を出力する。もしK番目に短い道筋がなければ、代わりに-1を出力しなければならない。
入力の例
2 2 1 2 5 2 1 4 1 2 2
出力の例
14
出典
POJ Monthly,Zeyuan Zhu