Problem J
Hittast

Mynd fengin af icelandair.com með leyfi

Álfur og Benedikt eru ástfangnir og vilja ekkert meira en að verja tíma sínum saman. Því miður búa þeir mjög langt í burtu frá hvorum öðrum. Álfur býr í Helsinki en Benedikt býr í Buenos Aires. Því geta þeir ekki bara hist hvenær sem er. Þeir ákveða því að skipuleggja hvar og hvenær þeir ætla sér að hittast.

Þeir hafa ákveðið dagsetningarnar nú þegar en þurfa aðstoð við val á staðsetningu. Þeim er í raun alveg sama hver staðsetningin er svo lengi sem þeir séu saman. Álfur er hinsvegar háskólanemi og hefur því mjög takmarkað fjármagn. Þess vegna biðja þeir þig um að finna ódýrustu lausnina fyrir sig.

Benedikt skrifaði niður lista af mögulegum staðsetningum til að hittast á og fann besta verðið á gistingu á hverjum stað fyrir sig. Hann fann einnig marga mismunandi ferðamöguleika milli staðsetninga. Álfur og Benedikt eru með mismunandi kreditkort og fá því mismunandi tilboð. Getur þú fundið ódýrasta kostinn fyrir elskhugana með þessum upplýsingum?

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ ($2 \leq n \leq 10^5$), fjölda staðsetninga sem koma til greina, og $m$ ($1 \leq m \leq 10^5$), fjölda mismunandi ferðaleiða milli staðsetninga. Helsinki er staðsetning $1$ og Buenos Aires er staðsetning $n$.

Önnur línan inniheldur $n$ heiltölur, $g_1, \dotsc , g_ n$, þar sem $g_ i$ táknar gistingarkostnaðinn á staðsetningu númer $i$.

Næst fylgja $m$ línur, þar sem hver lína inniheldur fjórar heiltölur $u$, $v$, $a$ og $b$, þar sem $u$ og $v$ eru staðsetningar sem má ferðast á milli í báðar áttir, $a$ er kostnaðurinn fyrir Álf að ferðast milli þessara staða og $b$ er kostnaðurinn fyrir Benedikt. Þar sem $u$ og $v$ tákna tvo mismunandi staði uppfylla gildin $1 \leq u, v \leq n$ og $u \neq v$. Benedikt skrifaði bara ódýrasta ferðamátann milli hverra staðsetninga þannig hvert par $u, v$ í inntakinu er einstakt. Þar sem ódýrasti kosturinn til að ferðast frá staðsetningu til hinnar sömu staðsetningu er $0$, kemur því aldrei fyrir lína þar sem endapunktarnir eru hinir sömu.

Öll verð í inntakinu eru á bilinu $0$ til $10^4$.

Það má gera ráð fyrir að það sé til bein eða óbein tenging frá hverri einustu staðsetningu til hverrar einustu annarar staðsetningu.

Úttak

Skrifaðu út eina heiltölu, verðið á ódýrasta ferðalaginu fyrir Álf og Benedikt.

Stigagjöf

2 1
10 1
1 2 50 60

51

4 6
1000 400 450 900
3 4 0 0
1 2 0 0
1 4 0 0
3 1 0 0
2 3 0 0
4 2 0 0

400

4 6
0 4 5 0
3 4 1 2
1 2 2 3
1 4 9 9
3 1 3 3
2 3 2 1
4 2 5 3

4