LQ 市的交通系統(tǒng)可以看成由 n 個(gè)結(jié)點(diǎn)和 m 條有向邊組成的有向圖。在每條邊上有一個(gè)信號(hào)燈，會(huì)不斷按綠黃紅黃綠黃紅黃... 的順序循環(huán) (初始時(shí)剛好變到綠燈)。當(dāng)信號(hào)燈為綠燈時(shí)允許正向通行，紅燈時(shí)允許反向通行，黃燈時(shí)不允許通行。每條邊上的信號(hào)燈的三種顏色的持續(xù)時(shí)長(zhǎng)都互相獨(dú)立，其中黃燈的持續(xù)時(shí)長(zhǎng)等同于走完路徑的耗時(shí)。當(dāng)走到一條邊上時(shí)，需要觀察邊上的信號(hào)燈，如果允許通行則可以通過此邊，在通行過程中不再受信號(hào)燈的影響；否則需要等待，直到允許通行。請(qǐng)問從結(jié)點(diǎn) s 到結(jié)點(diǎn) t 所需的最短時(shí)間是多少，如果 s 無法到達(dá) t 則輸出?1。

輸入的第一行包含四個(gè)整數(shù) n, m, s, t，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

接下來 m 行，每行包含五個(gè)整數(shù) u_i, v_i, g_i,r_i, d_i ，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔，分別表示一條邊的起點(diǎn)，終點(diǎn)，綠燈、紅燈的持續(xù)時(shí)長(zhǎng)和距離（黃燈的持續(xù)時(shí)長(zhǎng)）。

輸出一行包含一個(gè)整數(shù)表示從結(jié)點(diǎn) s 到達(dá) t 所需的最短時(shí)間。

4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1

11

對(duì)于 40% 的評(píng)測(cè)用例，n ≤ 500 ，1 ≤ g_i,r_i, d_i ≤ 100 ；

對(duì)于 70% 的評(píng)測(cè)用例，n ≤ 5000 ；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 100000 ，1 ≤ m ≤ 200000 ，1 ≤ s, t ≤ n ，1 ≤ u_i, v_i ≤ n ，1 ≤ g_i,r_i, d_i ≤ 10⁹ 。