23726번 - Time is Money 다국어

The city of ICPC has made excessive pedestrian separation, making transportation in the city quite complicated. Citizens of the ICPC city thus have big concern on efficient transportation to save time. The residents are eager to reach their destinations as fast as possible by repeating taxi rides on driveways and walks on footpaths.

Many cabstands are in the city. Footpaths and/or driveways directly connect some of the cabstand pairs allowing both-way traffic. Some pairs of cabstands may have no direct nor indirect paths.

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

• Walk a footpath, if any, to another cabstand, or
• Pick up a taxi, if any driveway connects the cabstand.

When you are on 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.

Transportation on a footpath or a driveway takes time defined for each of the roads. In addition, you have to wait one minute to pick up a taxi for the first time. The waiting time is doubled for each subsequent taxi picks, that is, two minutes for the second time, four minutes for the third time, and 2⁹⁹ minutes for the 100-th time.

You are initially at one of the cabstands on foot. Find the shortest time possible to reach the destination cabstand.

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, respectively. n is an integer between 2 and 20000, inclusive. Cabstands are numbered 1 through n. p and q are positive integers not exceeding 20000. a_i, b_i, and c_i describe the i-th footpath, meaning that it connects the cabstands numbered a_i and b_i, and it takes c_i minutes to walk. d_j, e_j, and f_j describe the j-th driveway, meaning that it connects the cabstands numbered d_j and e_j, and it takes a ride of f_j minutes. 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⁶.

The end of the input is indicated by a line containing three zeros. The total of n, the total of p, and the total of q of all the datasets do not exceed 200000, respectively.

For each dataset, output a single line containing the shortest time required in minutes for transporting from the cabstand number 1 to the cabstand number n modulo 10⁹+7. If such transportation is impossible, output −1 instead.