405005: GYM101736 E Easy

E for Easy.

Clearly, E for Easy sounds better than D for Deasy, F for Feasy, G for Geasy, or other such nonsense. Perhaps less clear is that E for Easy also sounds better than E for Empossible. It follows that the only logical title for this problem is Easy. Whether this problem is actually easy is up to you.

It is 23:16. The relentless rain pelting my window keeps me awake while I write this unintelligible mess. Although my fingers are moving across the k keys of the keyboard and pressing r keys that somehow translate to s complete albeit meaningless words, my mind is elsewhere. The rain outside just made me remember that nightmare I had w days ago. I was chasing my sanity down a network of p dank alleyways of some ghost town in the middle of a desert. My sanity was somewhere ahead of me, just outside of my reach. But this was only the prelude to the nightmare. As I chased my fleeing sanity into a tavern, I came face to face with a 40cm tall messenger pigeon. Frightened out of my wits, I awoke to the sound of birds chirping as if nothing had happened. Unfortunately, my sanity is still hiding inside the tavern.

The tavern has n rooms that are connected by m bidirectional halls. The n rooms are uniquely labeled with integers from 1 to n inclusive. The pigeon is in room 1, and my sanity is in room n. Each of the m halls require a certain amount of time to traverse. Even someone like me is able to follow these halls from 1 to n in the minimum amount of time possible. However, there are traps in each hall! Now, each hall only has an interval of time when it is safe to be in it. Should one set foot in a hall when it is unsafe, unthinkable things will happen.

I am unable to solve such a difficult problem, so it is up to you to determine the shortest amount of time it takes to go from the room where the pigeon is at to the room where my sanity is hiding. It is now time 0, let the search begin!

The first line contains two space-separated integers n and m (2 ≤ n ≤ 2·10⁵;1 ≤ m ≤ 2·10⁵), representing the number of rooms and halls respectively.

Each of the next m lines contains five space-separated integers a_i, b_i, c_i, d_i, and t_i (1 ≤ a_i, b_i ≤ n;0 ≤ c_i < d_i ≤ 10⁹;1 ≤ t_i ≤ 10⁹), describing the ith hall. This means the ith hall is between rooms a_i and b_i, it is safe to be in the hall from time c_i to time d_i inclusive and it takes t_i minutes to traverse the hall (in either direction). Two rooms could be connected by multiple halls. It is guaranteed that a_i ≠ b_i.

Output a single integer representing the shortest time it takes to go from room 1 to room n if it is possible to safely reach room n, or output -1 otherwise.

3 3
1 2 4 10 3
2 3 19 42 5
1 3 1 7 7

24

3 2
1 2 14 17 1
2 3 12 15 1

-1

In the first sample, the only way to reach the destination is by taking the halls from 1 to 2 and from 2 to 3. The journey can be as follows.

1. Time 0-4, wait 4 minutes in room 1
2. Time 4-7, take the hall from 1 to 2
3. Time 7-19, wait 12 minutes in room 2
4. Time 19-24, take the hall from 2 to 3