2905: 重重机关 [maze]（2）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
虹猫终于开启了迷宫的大门，守门人告诉虹猫迷宫里没有水和食物，因此虹猫必须以最快的速度救出蓝兔。守门人还把迷宫的一些情况告诉了虹猫。这座迷宫共有N个密室，入口密室编号为1，蓝兔所在的密室编号为N。各密室之间一共有M条单向密道。部分密道入口处有机关，这些机关最初是关闭的，一旦有人进入迷宫，所有机关就会按照预先设定的各自的时间间隔S和C循环关闭和开启。如果进入某条密道时恰好该密道入口处的机关处于开启状态，就会被机关困住，需要一定时间E才能挣脱机关继续前进。
除N号密室外，迷宫的所有地面都无法停留，否则地面就会陷落，虹猫只能马不停蹄地一直往前走。设虹猫进入迷宫的时刻为0，N个密室的通过时间可以忽略不计，通过密道则需要一定的时间T，请你帮助虹猫用最短的时间到达N号密室救出蓝兔。
除N号密室外，迷宫的所有地面都无法停留，否则地面就会陷落，虹猫只能马不停蹄地一直往前走。设虹猫进入迷宫的时刻为0，N个密室的通过时间可以忽略不计，通过密道则需要一定的时间T，请你帮助虹猫用最短的时间到达N号密室救出蓝兔。
Input
共M+1行，第一行为正整数N和M（中间用空格隔开）（1≤N≤10000，1≤M≤1000000），分别表示密室的数量和密道的数量。接下来共M行，每行有6个整数（中间用空格隔开），分别是U、V、T、S、C、E，其中U、V表示该条密道由密室U通往密室V（1≤U、V≤N）；T表示通过该密道需要T分钟（1≤T≤200）；S和C表示密道入口机关在有人进入迷宫S分钟后开启，保持开启状态C分钟后关闭，然后保持关闭状态S分钟后再度开启，循环往复（0≤S、C≤200，且S、C不同时为0）；E表示一旦被机关困住，需要E分钟才能挣脱机关继续前进（1≤E≤600）。
以下面的一行输入数据为例：
3 4 6 2 1 7
表示该密道从3号密室连接到4号密室，通过该密道需要6分钟，在有人进入迷宫后，该密道入口的机关在[0,2)时间区间为关闭状态（如果时刻t在 [a,b)时间区间，则有a≤t＜b），[2,3)时间区间为开启状态，[3,5)时间区间为关闭状态，循环往复。也就是说，如果虹猫在2分（含2分）到3分（不含3分）之间进入该密道，此时机关恰好是开启状态，他会被机关困住，需7分钟才能挣脱；而如果他在3分（含3分）到5分（不含5分）之间进入密道，则此时机关恰好是关闭状态，不会被机关困住。
以下面的一行输入数据为例：
3 4 6 2 1 7
表示该密道从3号密室连接到4号密室，通过该密道需要6分钟，在有人进入迷宫后，该密道入口的机关在[0,2)时间区间为关闭状态（如果时刻t在 [a,b)时间区间，则有a≤t＜b），[2,3)时间区间为开启状态，[3,5)时间区间为关闭状态，循环往复。也就是说，如果虹猫在2分（含2分）到3分（不含3分）之间进入该密道，此时机关恰好是开启状态，他会被机关困住，需7分钟才能挣脱；而如果他在3分（含3分）到5分（不含5分）之间进入密道，则此时机关恰好是关闭状态，不会被机关困住。
Output
一个正整数，表示虹猫到达N号密室的最短时间（单位分钟）
Sample Input Copy
4 5
1 2 1 3 2 2
1 3 5 4 2 6
2 1 2 3 0 3
2 4 3 0 1 5
3 4 6 2 1 7
Sample Output Copy
9
HINT
限制：
40%的数据，N≤100，M≤1000
100%的数据，N≤10000，M≤1000000
所有数据保证1号密室到N号密室连通。
40%的数据，N≤100，M≤1000
100%的数据，N≤10000，M≤1000000
所有数据保证1号密室到N号密室连通。