你是一位列車長，正在駕駛著一台火車開往左營。但是，不知名的魔法師施法讓鐵道上充滿了紓壓好玩的泡泡紙。

火車路網圖可以由一張有 $N$ 個節點的有向圖表示，其中，左營的編號為 $N$ 。對於第 $i$ 個節點的第 $j$ 條邊，它會有兩個參數 $t_{i,j},w_{i,j}$ ，分別表示那一條鐵道指向的節點以及這條鐵道的泡泡紙數量。
此外，對於每一個節點，剛開始時會由一個指針指著自己的第 $1$ 條鐵道。當火車抵達這個節點的時候，如果該節點不是 $N$ 號點，則火車會走向指針所指的鐵道。

但是，更換指針並不是不可能的。對於第 $i$ 個節點，如果付 $a_i$ 元給管理員，則它會將指針往右搬動 $x_i$ 格，而如果付 $b_i$ 元給管理員，則他會將指針往右搬動 $y_i$ 格，對於第 $i$ 個節點，移動指針的花費不能超過 $c_i$ 元。注意到，如果向右搬動之後超出該點的鐵道數量的話，會繞回第一條鐵道繼續搬動（也就是說，假設指針目前在 $p$ ，第 $i$ 個點出度為 $d_i$，那付一次 $a_i$ 元可以把 $p$ 變為 $(p+x_i-1)\text{ mod }d_i+1$，付一次 $b_i$ 元可以把 $p$ 變為 $(p+y_i-1)\text{ mod }d_i+1$）。可以付多次 $a_i$ 與 $b_i$ 來搬動指針

身為一位盡責的列車長，當你從出發站前往左營時，你抵達左營所經過的距離必須是在所有合法移動指針的方法中，該點至左營的最短距離，也就是說，不能存在一條路徑長度比你所走的路徑還要短。
你最喜歡泡泡紙被火車那強壯有力的輪子輾過所發出的哀嚎了，因此，你想要知道，對於所有車站，如果你都沿著最短路徑走，並且在第 $i$ 個車站花費不超過 $c_i$ 元，則你最多可以壓過多少張泡泡紙？
但是，鐵路會有無法抵達左營的情況，或者是無法在各節點花費分別不超過 $c_i$ 的情況抵達的狀況，此時，請輸出 -1。