E - 遅刻厳禁
問題文
ストーリー
同志社大学今出川キャンパスは地下鉄今出川駅直結です。
高橋君が住む町には駅 $1,$ 駅 $2,$ $...,$ 駅 $N$ の $N$ 個の駅があります。
高橋君の家から駅 $i \ (1 ≤ i ≤ N)$ までは歩いて $y_i$ 分で移動できます。
また、$M$ 本の電車が走っており、$j \ (1 ≤ j ≤ M)$ 番目の電車を使うと駅 $u_j$ と 駅 $v_j$ を双方向に $c_j$ 分で移動できます。
ただし、電車を待つ時間は無視できます。
高橋君は大学の授業のために $9$ 月 $d_1$ 日 $h_1$ 時 $m_1$ 分に家を出発し、徒歩と電車を使って大学のある駅 $N$ に行きます。
大学の授業は $9$ 月 $d_2$ 日 $h_2$ 時 $m_2$ 分に始まります。
$1$ 日は $24$ 時間、$1$ 時間は $60$ 分です。
また、時刻は $24$ 時間表記で与えられます。
高橋君が大学がある駅 $N$ に授業開始時刻までに到着できるか判定し、到着できるならその最も早い日時を出力してください。
なお、高橋君の大学は駅 $N$ からすぐに到着できるので、駅 $N$ から大学までの距離は考えなくてよいものとします。
制約
- $2 ≤ N, M ≤ 10^5$
- $1 ≤ y_i ≤ 10^{4}$
- $1 ≤ u_j,v_j ≤ N$
- $u_j ≠ v_j$
- $1 ≤ c_j ≤ 10^{4}$
- $1 ≤ d_1 ≤ d_2 ≤ 30 $
- $0 ≤ h_1, h_2 ≤ 23 $
- $0 ≤ m_1, m_2 ≤ 59 $
- $d_1=d_2$ のとき $h_1 < h_2$ 、もしくは $h_1=h_2$ かつ $m_1 < m_2$
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N \ M$
$y_1 \ y_2 \ \dots \ y_N$
$u_1 \ v_1 \ c_1$
$u_2 \ v_2 \ c_2$
$\vdots$
$u_M \ v_M \ c_M$
$d_1 \ h_1 \ m_1$
$d_2 \ h_2 \ m_2$
出力
高橋君が駅 $N$ に授業開始時刻までに到着でき、その最も早い日時が $d'$日 $h'$時 $m'$分であるとき、$d',h',m'$ をこの順に空白区切りで出力してください。
駅 $N$ に授業開始時刻までに到着できないなら -1 を出力してください。
3 2
5 10 15
1 2 6
2 3 3
2 12 50
2 14 33
2 13 3
高橋君の家から駅 $N$ まで最も早く到着するには以下のように移動します。
- 家から駅 $2$ まで歩いて $10$ 分で移動する
- 駅 $2$ から駅 $3$ まで電車を使い $3$ 分で移動する
合計 $13$ 分で移動できるので、$2$ 日 $12$ 時 $50$ 分の $13$ 分後である $2$ 日 $13$ 時 $3$ 分に駅 $N$ に到着できます。
3 2
5000 10000 10000
1 2 6000
3 2 3000
29 23 50
30 3 20
-1
授業開始時刻までに駅 $N$ に到着することはできません。
$y_i$ と $c_j$ は $60$ より大きくなることがあります。
4 4
5 20 15 200
1 2 6
2 1 12
2 3 4
3 4 88
2 12 50
2 14 33
2 14 33
授業開始時刻ちょうどに到着してもよいです。