시간은 돈이다

ICPC 시에는 보행자 분리 시설이 지나치게 많아서 도시 교통이 매우 복잡하다. 시민들은 시간을 아끼고 싶어 하며, 차도에서 택시를 타는 것과 보도에서 걷는 것을 번갈아 반복해서 가능한 한 빨리 목적지에 도착하려고 한다.

도시에는 택시 승강장이 많이 있다. 보도와 차도는 일부 승강장 쌍을 직접 잇고, 두 방향 모두 통행할 수 있다. 승강장 쌍 중에는 직접 연결도 없고 간접 연결도 없는 경우가 있을 수 있다.

승강장에서 걷고 있을 때는 다음 중 하나를 할 수 있다.

• 보도가 있다면 그 보도를 걸어 다른 승강장으로 간다.
• 차도가 그 승강장에 연결되어 있다면 택시를 잡는다.

택시를 타고 있을 때는 다음 중 하나를 할 수 있다.

• 차도를 따라 다른 승강장까지 계속 탄다.
• 택시에서 내린다.

택시에서 내릴 수 있는 곳은 승강장뿐이다.

보도나 차도로 이동하는 데는 각 도로마다 정해진 시간이 걸린다. 여기에 더해, 택시를 처음 잡을 때는 1분을 기다려야 한다. 이후 택시를 잡을 때마다 대기 시간이 두 배가 되어, 두 번째는 2분, 세 번째는 4분, 100번째는 $2^{99}$분이다.

처음에는 승강장 1에서 걷고 있다. 승강장 $n$에 도착하는 데 걸리는 최단 시간을 구하라. 답은 $10^9+7$로 나눈 나머지로 출력한다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식을 따른다.

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

여기서 $n$, $p$, $q$는 각각 승강장, 보도, 차도의 개수이다. $n$은 2 이상 20000 이하의 정수이다. 승강장은 1부터 $n$까지 번호가 매겨져 있다. $p$와 $q$는 20000 이하의 양의 정수이다. $i$번째 보도는 승강장 $a_i$와 $b_i$를 잇고, 걷는 데 $c_i$분이 걸린다. $j$번째 차도는 승강장 $d_j$와 $e_j$를 잇고, 타고 가는 데 $f_j$분이 걸린다. $a_i$, $b_i$, $d_j$, $e_j$는 $n$ 이하의 양의 정수이다. $c_i$와 $f_j$는 $10^6$ 이하의 양의 정수이다.

입력의 끝은 0 세 개가 들어 있는 줄로 표시된다. 모든 데이터셋에 대해 $n$의 합, $p$의 합, $q$의 합은 각각 200000을 넘지 않는다.

각 데이터셋에 대해 승강장 1에서 승강장 $n$까지 가는 데 걸리는 최단 시간을 분 단위로 한 줄에 출력한다. 시간은 $10^9+7$로 나눈 나머지로 출력한다. 이동이 불가능하면 -1을 출력한다.