Problem
ヴァシュキ地方のいくつかの村の間にはバスがあります。ここの乗客数はそれほど多くないため、バスは 1 日に数本しか運行していません。
マリア・イワノフナはできるだけ早く村 d から村 v に移動する必要があります (彼女は時刻 0 に村 d にいると見なされます)。
入力
最初に数値 N を入力します –村の総数 (1 <= N <= 100), 次に、村の番号 d と v、 その後にバストリップ数 R (0 <= R <= 10000) が続きます。以下はバス路線の説明です。各フライトは、出発地の番号、出発時間、目的地の村、到着時間で指定されます (すべての時間 – は 0 から 10000 までの整数です)。時間 t に乗客が村に到着した場合、t からいつでも出発できます。
出力
マリア・イワノフナが村にいることができる最短時間を出力してください v.指定されたバス ルートを使用して d から v に移動できない場合は、-1 を出力します。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |