Time is Money

The city of ICPC has excessive pedestrian separation, which makes transportation in the city quite complicated. Citizens want to save time, so they try to reach their destinations as fast as possible by alternating between taxi rides on driveways and walks on footpaths.

Many cabstands are in the city. Footpaths and driveways connect some pairs of cabstands directly, and both allow traffic in both directions. Some pairs of cabstands may have no direct or indirect path between them.

When you are on foot at a cabstand, you can either:

• walk a footpath, if one exists, to another cabstand, or
• pick up a taxi, if a driveway connects to the cabstand.

When you are in a taxi, you can either:

• keep riding to another cabstand via a driveway, or
• get out of the taxi.

You can get out of a taxi only at cabstands.

Traveling a footpath or a driveway takes the time given for that road. In addition, you wait one minute the first time you pick up a taxi. The wait doubles with each later pickup: two minutes the second time, four minutes the third time, and $2^{99}$ minutes the 100th time.

You start on foot at cabstand 1. Find the shortest possible time to reach cabstand $n$. Output the answer modulo $10^9+7$.

The input consists of multiple datasets, each in the following format.

n p q
a1 b1 c1
…
ap bp cp
d1 e1 f1
…
dq eq fq

Here, $n$, $p$, and $q$ are the numbers of cabstands, footpaths, and driveways. $n$ is an integer from 2 to 20000, inclusive. Cabstands are numbered 1 through $n$. $p$ and $q$ are positive integers not exceeding 20000. Footpath $i$ connects cabstands $a_i$ and $b_i$ and takes $c_i$ minutes to walk. Driveway $j$ connects cabstands $d_j$ and $e_j$ and takes $f_j$ minutes to ride. All $a_i$, $b_i$, $d_j$, and $e_j$ are positive integers not exceeding $n$. $c_i$ and $f_j$ are positive integers not exceeding $10^6$.

The input ends with a line containing three zeros. The totals of $n$, of $p$, and of $q$ over all datasets each do not exceed 200000.

For each dataset, output one line with the shortest time in minutes to travel from cabstand 1 to cabstand $n$, modulo $10^9+7$. If the trip is impossible, output -1.