Verkefni

Snákurinn JOI-kun hefur villst inn í stórt setur. Áður en íbúar setursins uppgötva hann verður hann að komast út úr setrinu.

Í þessu setri eru $N$ herbergi, númeruð $1, 2, \dots, N$. Einnig eru þar $M$ gangar, og tengir $i$-ti gangurinn ($1 \le i \le M$) saman herbergi $A_i$ og herbergi $B_i$. JOI-kun getur farið um þessa ganga í báðar áttir og það tekur $D_i$ mínútur að fara um gang $i$. Engin önnur leið er til að ferðast á milli herbergja en að fara um gangana.

Hitastigi hvers herbergis í setrinu er haldið stöðugu og er það fyrir JOI-kun annaðhvort of kalt, þægilegt eða of heitt. Þar sem JOI-kun þolir ekki snöggar hitabreytingar getur hann ekki farið inn í of heitt herbergi þegar liðnar eru færri en $X$ mínútur síðan hann fór síðast út úr of köldu herbergi. Á sama hátt getur hann ekki farið inn í of kalt herbergi þegar liðnar eru færri en $X$ mínútur síðan hann fór síðast út úr of heitu herbergi.

Á ferð sinni verður JOI-kun að fara strax út úr herbergi um leið og hann kemur inn í það. Einnig getur hann hvorki snúið við á miðjum gangi né verið lengur en $D_i$ mínútur að fara um gang $i$. Hins vegar er honum heimilt að fara aftur inn í herbergi sem hann hefur þegar heimsótt, eða nota aftur gang sem hann hefur þegar farið um.

JOI-kun er núna í herbergi $1$. Þetta herbergi er of kalt fyrir JOI-kun. Um leið og JOI-kun kemur inn í herbergi $N$, þar sem útgönguleiðin úr setrinu er, kemst hann út úr setrinu.

Finndu stysta tímann sem það tekur JOI-kun að komast út úr setrinu.

Inntak

Inntakið samanstendur af $1 + N + M$ línum.

Í línu $1$ standa $3$ heiltölur $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) aðskildar með bilum. Þetta táknar að í setrinu séu $N$ herbergi og $M$ gangar, og að það taki JOI-kun $X$ mínútur að aðlagast hitabreytingum.

Í $i$-tu línu ($1 \le i \le N$) af næstu $N$ línum stendur heiltala $T_i$ ($0 \le T_i \le 2$) sem táknar hitastig herbergis $i$. Fyrir JOI-kun er herbergi $i$ of kalt þegar $T_i = 0$, þægilegt þegar $T_i = 1$ og of heitt þegar $T_i = 2$. Tryggt er að $T_1 = 0$.

Í $j$-tu línu ($1 \le j \le M$) af næstu $M$ línum standa $3$ heiltölur $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) aðskildar með bilum. Þetta táknar að gangur $j$ tengi saman herbergi $A_j$ og herbergi $B_j$, og að það taki $D_j$ mínútur að fara um hann. Athugið að það geta verið fleiri en einn gangur sem tengja saman sama herbergjaparið.

Í gefnum inntaksgögnum er tryggt að JOI-kun geti komist út úr setrinu.

Úttak

Prentaðu í $1$ línu heiltölu sem táknar lágmarksfjölda mínútna sem það tekur JOI-kun að komast út úr setrinu.

Dæmi um inntak og úttak

Inntaksdæmi 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

Úttaksdæmi 1

9

Inntaksdæmi 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

Úttaksdæmi 2

6

Í inntaksdæmi 1 er styst að fara um herbergin í röðinni $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

Í inntaksdæmi 2 eru nokkur herbergjapör (til dæmis herbergi $1$ og herbergi $5$) tengd saman með fleiri en einum gangi.