D. The Gingerbread Man and Traffic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While fleeing from his pursuers, the Gingerbread Man shouts, "Run, run as fast as you can! You can't catch me. I'm the Gingerbread Man!"

However, you're not so sure about the Gingerbread Man's claim. Unfortunately for him, he is trying to escape in a busy city with lots of traffic lights.

The city can be thought of as a collection of $$$n$$$ traffic intersections connected by $$$m$$$ two-way roads, where the intersections are numbered from $$$1$$$ to $$$n$$$. The roads are also numbered from $$$1$$$ to $$$m$$$, with the $$$i$$$-th road having a length of $$$l_i$$$ units. The Gingerbread Man runs at a rate of $$$1$$$ unit per second.

The Gingerbread Man is currently at the first intersection and wants to reach intersection $$$n$$$ by traveling through the roads, and he can only pass through an intersection when the traffic light is red; when the light is green, he must wait at the intersection for cars to pass. Initially, all traffic lights have just turned red. The traffic light at the $$$i$$$-th intersection alternates between displaying red for $$$r_i$$$ seconds and green for $$$g_i$$$ seconds. If the Gingerbread Man arrives at the intersection when the light is transitioning from red to green, he must wait.

Since you are skeptical about the Gingerbread Man's ability to run, you would like to figure out the fastest time it takes the Gingerbread Man to reach intersection $$$n$$$. It is guaranteed that a path exists from the first intersection to the $$$n$$$-th intersection.

Input

The first line contains $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — the number of intersections and the number of roads, respectively.

The next $$$n$$$ lines contain two integers each, the $$$i$$$-th of which contains $$$r_i$$$ ($$$1 \leq r_i \leq 10^4$$$) and $$$g_i$$$ ($$$1 \leq g_i \leq 10^4$$$) — the respective durations of red and green lights at intersection $$$i$$$.

The following $$$m$$$ lines contain three integers each, the $$$i$$$-th of which contains $$$u_i$$$ ($$$1 \le u_i \le n$$$), $$$v_i$$$ ($$$1 \le v_i \le n$$$), and $$$l_i$$$ ($$$1 \leq l_i \leq 10^4$$$), indicating a road of length $$$l_i$$$ between intersections $$$u_i$$$ and $$$v_i$$$. It is guaranteed that $$$u_i$$$ and $$$v_i$$$ are distinct.

Output

Output a single integer representing the least amount of seconds it takes the Gingerbread Man to run from intersection $$$1$$$ to intersection $$$n$$$.

Example
Input
3 2
1 1
1 1
1 1
1 2 1
2 3 1
Output
3
Note

In the sample, the Gingerbread Man reaches intersection $$$2$$$ after one second, but the light at that intersection turns green when he arrives, so he must wait one second. After waiting, he then takes one second to reach intersection $$$3$$$, so in total he takes at least $$$3$$$ seconds to reach his destination.