Problem L
Stysti skógarleiðangurinn

Mynd fengin af leagueoflegends.fandom.com

Þeir Arnar og Sammi eru miklir Deild Goðsagnanna spilarar og hafa þeir verið að spila leikinn í óratíma. Þótt margir trúa því ekki þá er Deild Goðsagnanna liðaleikur og skiptir því miklu máli að hjálpa liðsfélögum. Þar sem Sammi er skógarspilari þá spilar hann mikilvægasta hlutverkið við að hjálpa liðsfélögum, þar er markmiðið hans að berjast við skógarskrímsli og koma á brautir liðsfélaga til að hjálpa þeim að senda óvininn aftur í bruninn sinn. Hann Arnar er hinsvegar árasarskaðaspilari og elskar því ekkert meira en að senda óvinina aftur í bruninn sinn og biður því Samma um að koma á brautina sína eins hratt og hann getur. Samma finnst samt mikilvægara að berjast við öll skógarskrímslin fyrst, áður en hann kemur að heimsækja brautir liðsfélaga. Hann vill samt ekki láta Arnar bíða óþarflega lengi og fer því alltaf stystu leiðina við að berjast við öll skógarskrímslin.

Höfundar leiksins eru byrjaðir að gera verkefnið mikið erfiðara fyrir hann Samma, þeir eru byrjaðir að breyta öllum skógarleiðunum og veit Arnar því ekki lengur hversu lengi hann Sammi er að berjast við öll skógarskrímslin. Þar sem Sammi er of upptekin við það að berjast við öll skógarskrímslin og hann Arnar of upptekin við að halda sér úr brunninum sínum. Þá biður Arnar þig um hjálp við að finna hversu lengi Sammi er að klára að berjast við öll skógarskrímslin svo hann veit hversu lengi hann þarf að bíða eftur hjálp frá Samma.

Ekki má gleyma að Sammi fær alltaf hjálp við fyrsta skrímslið sitt og byrjar því alltaf á sama skrímslinu. Ásamt því getur Sammi stundum notað aukakraftinn sinn, ljósta. Þegar Sammi notar ljósta á skrímsli þá klárast bardaginn strax og þarf því ekki að stoppa og berjast við það með hefðbundnu kröftunum sínum.

Inntak

Fyrsta línan í inntakinu inniheldur þrjár heiltölur $n, m$ og $s$, þar sem $n$ er fjöldi skrímsla, $m$ er fjöldi skógarleiða og $s$ fjöldi ljósta sem Sammi getur notað. Næst fylgir ein lína með $n$ heiltölum þar sem hver heiltala $1 \leq x_ i \leq 10^4$ táknar tímann sem það tekur Samma að berjast við skrímsli númer $i$. Svo fylgja $m$ línur þar sem hver lína inniheldur þrjár heiltölur $u, v$ og $t$, Sem táknar leið frá skrímsli $u$ til skrímsli $v$ sem tekur $1 \leq t \leq 10^4$ langan tíma að fara á milli.

Úttak

Skrifaðu út stysta tímann sem það tekur að berjast við öll skógarskrímslin ef hann Sammi byrjar á skrímsli númer $1$.

Stigagjöf

2 1 1
10 3
1 2 10

13

4 4 1
1 2 3 4
1 3 3
1 2 5
2 4 4
1 4 10

21