N M K
S G
a_0 b_0 d_0
a_1 b_1 d_1
:
a_{M-1} b_{M-1} d_{M-1}
x_0 f_0
x_1 f_1
:
x_{K-1} f_{K-1}

• 1行目には、駅の数N、路線の数M、運賃表のサイズKが与えられる。
• 2行目には、出発駅の番号S、到着駅の番号Gが与えられる。
• 3行目からM+2行目には、路線の情報が与えられる。各行は、駅a_iとb_iを結ぶ、距離d_iの路線が存在することを表す。
• M+3行目からM+K+2行目には、運賃表の情報が与えられる。任意のj\ (0≦j＜K)および距離l\ (l≧1)について、x_j≦l＜x_{j+1}を満たすならば、距離lに対する運賃がf_jであることを表す。ただし、x_Kは無限大であると仮定する。

• 2≦N≦30000
• 1≦M≦60000
• 1≦K≦100
• 0≦S＜N
• 0≦G＜N
• S≠G
• 任意の0≦i＜Mに対し、0≦a_i＜N,\ 0≦b_i＜N,\ a_i≠b_i
• 任意の0≦i＜j＜Mに対し、\{a_i,b_i\}≠\{a_j,b_j\}
• 任意の0≦i＜Mに対し、1≦d_i≦10^4
• 1=x_0＜x_1＜...＜x_{K-1}≦10^9
• 1≦f_0＜f_1＜...＜f_{K-1}≦10^9
• 駅Sから駅Gへの経路が存在する

• 2≦N≦100
• 1≦M≦200
• 切符分割により交通費が安くなることはない。 すなわち、駅Sから駅Gまでの切符1枚のみを購入するのが最適となる。

• 2≦N≦100
• 1≦M≦200