CODE FESTIVAL 2015 予選A 予想問題

昨夜、会場までの移動時間が4時間かかるかからないがTLで話題になってたので、予選AのDぐらいにこういう問題来るんでないかなーと。

問題

tkhs君はCODE FESTIVALへの参加を考えている。CODE FESTIVALでは自宅から東京駅へ行くまでの所要時間がT分以上であると前泊の費用を主催者であるR社が負担してくれる。tkhs君は万全の状態でコンテストに臨むために前泊したいのだが、自宅から東京駅まで行くのにT分以上かかりそうもない。そこでtkhs君は歩く速さを調整することで自宅から東京駅に行くまでにかかる時間が最短でT分になるように調整するようにした。
tkhs君は電車または徒歩で移動する。歩く速さは体力の範囲内で自由に決められるが、CODE FESTIVALの参加規約上、東京駅までの経路は時間が最短になるような経路を選ばなくてはならない。電車はtkhs君が乗ると直ちに出発し、遅延は無いものとする。また、電車の乗降にかかる時間は無視してよい。

入力

N T E W V
ta_1 tb_1 tt_1
...
ta_E tb_E tt_E
wa_1 wb_1 wd_1
...
wa_W wb_W wd_W

一行目に自宅、東京駅、及び経由地点の合計の数 N、前泊が可能となる移動時間 T分、 電車の区間数 E、 徒歩で行動できる区関数 W、tkhs君の歩く最速の速さ V[m/min.] が与えられる。
各地点には0からN-1の番号が振られている。
自宅は番号0, 東京駅は番号 N-1の地点である。
続くT行に、電車で移動できる区間を表す情報が与えられる。ta_i, tb_i間 は電車で移動でき、その所要時間はtt_i分である。
続くW行に、徒歩で移動できる区間を表す情報が与えられる。wa_i, wb_i間 は徒歩で移動でき、その移動距離はwd_iメートルである。

出力

自宅から東京駅までの移動に最短でちょうどT分かかるような歩く速さ v [m/min.]を一行に出力せよ。
そのような v が存在しない場合、またはそのようなvが複数存在する場合は -1 を出力せよ。
期待される出力との差が10^{-6}以下であれば正解とみなされる。

入力例

9 30 6 5 600
1 2 3
2 4 10
3 5 15
3 6 8
6 8 20
7 8 2
0 1 200
1 3 10000
3 4 3000
4 7 500
5 8 500

こんなんです

出力例

作る気力なかった

解法

にぶたん+dijkstraで解けるんでないかなーと思ってる。もっといい方法があると厳しめな制約つけれそう。