Gefið er net með $N$ hnútum og $M$ óstefndum leggjum. Hver leggur $i$ hefur ferðastig $W_i$ og tengir hnútana $U_i$ og $V_i$.

Bob má færa sig úr einum hnúti í annan með því að nota leggi. Bob getur notað $i$-ta legginn ef og aðeins ef stig hans eru meiri en eða jöfn $W_i$. Hann getur notað sama legginn og heimsótt sama hnútinn eins oft og hann vill.

Hvenær sem Bob er staddur í hnúti $x$ hefur hann tvo valkosti til að afla sér nýrra stiga:

• Hann getur fengið $A_x$ stig ókeypis. Hann getur aðeins notað þennan valkost einu sinni á ferðalagi sínu.
• Hann getur fengið $1$ stig fyrir $C_x$ peninga. Hann getur notað þennan valkost eins oft og hann vill á öllu ferðalagi sínu.

Bob er nú með $Q$ fyrirspurnir. Fyrir hverja fyrirspurn $i$, svaraðu eftirfarandi spurningu:

• Bob er með upphafsstig $R_i$ og er staddur í hnúti $S_i$. Hann ætlar að komast í hnút $T_i$. Hver er lágmarksfjöldi peninga sem þarf til þess?

Prentaðu $-1$ ef hann getur ekki komist í hnút $T_i$ jafnvel með óendanlegum fjölda peninga.

Inntak

• Fyrsta línan inniheldur eina heiltölu $T$ ($1 \le T \le 100$), fjölda prófunartilvika.
• Síðan, fyrir hvert prófunartilvik:
  • Fyrsta línan inniheldur þrjár heiltölur aðskildar með bili $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$).
  • Önnur línan inniheldur $N$ heiltölur aðskildar með bili $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$).
  • Þriðja línan inniheldur $N$ heiltölur aðskildar með bili $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$).
  • Síðan fylgja $M$ línur, þar sem hver lína inniheldur þrjár heiltölur aðskildar með bili $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$).
  • Síðan fylgja $Q$ línur, þar sem hver lína inniheldur þrjár heiltölur aðskildar með bili $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$).

Tryggt er að summa $N$ yfir öll prófunartilvik fari ekki yfir $5 \cdot 10^5$.

Tryggt er að summa $M$ yfir öll prófunartilvik fari ekki yfir $5 \cdot 10^5$.

Tryggt er að summa $Q$ yfir öll prófunartilvik fari ekki yfir $5 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta $Q$ línur, þar sem hver lína samanstendur af einni heiltölu, svarinu við þeirri fyrirspurn.

Dæmi

Dæmi um inntak 1

1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10

Dæmi um úttak 1

11
0
4
5