Round Trip

Jim plans to visit one of his best friends, who lives in a town in the mountains. He first leaves his hometown and travels to the destination town; this is the go phase. He then travels back to his hometown; this is the return phase. Write a program that computes the minimum total cost of the whole trip, where the total cost is the sum of the cost of the go phase and the cost of the return phase.

The towns form a network that includes the hometown and the destination. Every road is one-way and may be traveled only in its given direction. Traveling a road costs a fixed amount.

Besides the road costs, you must pay a visa fee to pass through each town along the way. Because it is a visa fee, you pay it only on your first visit to a town; the second and later visits to the same town are free.

Each town has an altitude. During the go phase you may not descend: when moving from town $a$ to town $b$, the altitude of $a$ must not exceed that of $b$. During the return phase you may not ascend: the altitude of $a$ must not be less than that of $b$. If $a$ and $b$ have equal altitude, the road from $a$ to $b$ may be used in both phases.

The input consists of several datasets. Each dataset has the following format.

n m
d2 e2
d3 e3
...
d(n-1) e(n-1)
a1 b1 c1
a2 b2 c2
...
am bm cm

Every value is a non-negative integer, and values on the same line are separated by a single space.

$n$ is the number of towns and $m$ is the number of one-way roads, with $2 \le n \le 50$ and $0 \le m \le n(n-1)$. Towns are numbered $1$ through $n$. Town $1$ is the hometown and town $n$ is the destination.

For each town $i$ with $2 \le i \le n-1$, $d_i$ is its visa fee and $e_i$ is its altitude, with $1 \le d_i \le 1000$ and $1 \le e_i \le 999$. Towns $1$ and $n$ charge no visa fee. The altitude of town $1$ is $0$ and the altitude of town $n$ is $1000$. Several towns may share the same altitude, but at most $10$ towns share any single altitude.

The $j$-th road goes from town $a_j$ to town $b_j$ and costs $c_j$, with $1 \le a_j \le n$, $1 \le b_j \le n$, and $1 \le c_j \le 1000$. You may travel from $a_j$ to $b_j$ but not from $b_j$ to $a_j$ unless a separate road is given. No two roads share the same ordered pair of endpoints, and no road connects a town to itself.

The last dataset is followed by a line containing two zeros separated by a space; that line is not part of the data to process.

For each dataset, output a single line containing the minimum total cost of the trip, including visa fees. If no valid trip exists, output $-1$.