ICPC 市は歩車分離を進め過ぎたため，市内の移動が複雑で面倒になってしまった． そのため市民は移動時間を短縮することへの関心が高くなっている． 人々はタクシーに乗って車道を行くのと歩道を歩いて行くのを上手に繰り返して， できるだけ早く目的地に到着したいと考えている．

ICPC 市にはたくさんのタクシースタンドがある． いくつかのタクシースタンドの間には直接双方向に行き来できる歩道や車道がある． すべてのタクシースタンドの間に直接・間接の経路が必ずあるとは限らない．

タクシースタンドにいてタクシーに乗っていないときは，

• そこにつながる歩道があればその道を歩いて移動すること， または
• そこにつながる車道があればその場でタクシーに乗り込むこと

ができる．タクシーに乗っているときは，

• 現在乗っているタクシーのまま車道でつながっている別のスタンドに移動すること，または
• その場でタクシーを降りること

ができる． タクシースタンド以外ではタクシーを降りられない．

歩道や車道を移動するとき，その道ごとに決まった時間がかかる． また，タクシーは乗るときに待ち時間がかかる． 待ち時間は，初めてタクシーに乗るときは 1 分， 以降は直前の待ち時間の 2 倍である． つまり 2 回目に乗るときは 2 分，3 回目に乗るときは 4 分, 100 回目に乗るときは 2⁹⁹ 分かかる．

あなたは最初タクシースタンドのひとつにいて，タクシーには乗っていない． そこから目的地のタクシースタンドまでの移動にかかる最短時間を求めなさい．

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n p q
a₁ b₁ c₁
…
a_p b_p c_p
d₁ e₁ f₁
…
d_q e_q f_q

n, p, qはそれぞれタクシースタンドの数， 歩道の数，車道の数を表す． n は，2 以上の整数であり，20000 を超えない． タクシースタンドには 1 から n までの番号がついている． p, q は，どちらも正の整数であり，20000 を超えない． a_i, b_i, c_i は i 番目の歩道を表す．それは a_i 番と b_i 番のタクシースタンドを結んでおり， 歩いて移動すると c_i 分かかる． d_j, e_j, f_j は j 番目の車道を表す．それは d_j 番と e_j 番のタクシースタンドを結んでいて， タクシーに乗って f_j 分かかる． a_i, b_i, d_j, e_j はそれぞれ 1 以上 n 以下の整数である． c_i, f_j はそれぞれ 1 以上 10⁶ 以下の整数である．

入力の終わりは，3 つのゼロからなる行で表される． 全データセットについての n の合計，p の合計， q の合計はそれぞれ 200000 を超えない．

各データセットについて， タクシースタンド 1 番からタクシースタンド n 番までの移動にかかる最短時間を分単位で表したものを 10⁹+7 で割った余りを 1 行に出力せよ． 移動が不可能な場合は −1 を出力せよ．

5 4 2
1 2 1
2 3 100
3 4 1
4 5 100
2 3 10
4 5 10
4 1 1
1 2 100
2 3 100
4 3 3
1 2 10
2 3 1
3 4 10
2 1 2
3 2 2
4 3 2
0 0 0

25
-1
7