The Hero

Byteotheus, the most famous hero of Byteotia, has won another battle. While his crew loads the ship with the spoils, he sits in his cabin and plans the way back to his home island, The Bitaca. That is not an easy task. Many gods envy his popularity and would gladly take him down a peg. A few of them favour him, the goddess Bythena above all. It was Bythena who sent Byteotheus a dream last night to warn him about the dangers ahead.

The Byteonian Sea has $n$ islands, numbered from 1 to $n$. The ship is now at island 1 and its destination is The Bitaca, island $n$. Some pairs of islands are joined by one-way sea routes, numbered from 1 to $m$. Route $i$ leads from island $a_i$ to island $b_i$ and takes exactly $d_i$ days. At most 10 routes start at any single island.

If the ship leaves island $a_i$ along route $i$ at dawn on day $j$, it reaches island $b_i$ at dawn on day $j + d_i$. The ship may stay at any island as long as it likes. Before reaching the next island it cannot leave the chosen route, and it cannot stay at sea longer than the route takes. The earliest moment Byteotheus can leave island 1 is dawn on day 1.

Bythena's warning was precise. She gave Byteotheus the exact list of the $p$ traps the gods have prepared. Each trap sits on one island and is active during one period. Trap $i$ is on island $w_i$ and is active from day $s_i$ through day $k_i$, day $k_i$ included. If the ship is on an island while a trap there is active, nobody survives. The Bitaca has no traps, and no trap on island 1 is active on day 1.

If the ship reaches an island at dawn on day $x$ and leaves it at dawn on day $y$, it counts as being on that island on every day from $x$ to $y$, both included. A trap on that island active on any of those days kills the crew.

Byteotheus wants a way home that avoids every trap, and he also wants to know how much longer the traps make his voyage. Find the smallest number of days he needs to reach The Bitaca safely.

The first line contains two integers $n$ and $m$ ($2 \le n \le 100\,000$, $1 \le m \le 1\,000\,000$), the number of islands and the number of sea routes. Each of the next $m$ lines describes one route with three integers $a_i$, $b_i$, $d_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 10^9$), meaning that route $i$ leads from island $a_i$ to island $b_i$ and takes $d_i$ days. All routes are one way. At most 10 routes start at any single island.

The next line contains one integer $p$ ($0 \le p \le 100\,000$), the number of traps. Each of the next $p$ lines describes one trap with three integers $w_i$, $s_i$, $k_i$ ($1 \le w_i < n$, $1 \le s_i \le k_i \le 10^9$), meaning that trap $i$ is on island $w_i$ and is active from day $s_i$ through day $k_i$. If $w_i = 1$, then $s_i > 1$.

If no route avoids every trap, print NIE on a single line. That is Polish for no. Otherwise print one integer $d$, the smallest number of days the voyage takes. The ship then reaches The Bitaca at dawn on day $d + 1$.

In the first example Byteotheus leaves island 1 at dawn on day 1 and reaches island 2 on day 4. He waits one day, sails for island 3 and arrives on day 6, then turns back to island 2 at once. On day 8 he leaves island 2 for island 4, arrives on day 10, and reaches The Bitaca on day 11.