Есептің шарты

Жылан JOI-кун үлкен бір зәулім үйге адасып кіріп кетті. Үй тұрғындары байқап қалмай тұрғанда, ол зәулім үйден қашып шығуы керек.

Бұл зәулім үйде $1, 2, \dots, N$ сандарымен нөмірленген $N$ бөлме бар. Сондай-ақ $M$ дәліз бар, мұндағы $i$-ші дәліз ($1 \le i \le M$) $A_i$ бөлмесі мен $B_i$ бөлмесін жалғайды. JOI-кун бұл дәліздермен екі бағытта да жүре алады, ал $i$-ші дәлізбен өтуге $D_i$ минут уақыт кетеді. Бөлме мен бөлменің арасында дәліз арқылы өтуден басқа қозғалу тәсілі жоқ.

Бұл зәулім үйдегі әр бөлменің температурасы тұрақты деңгейде реттелген: JOI-кун үшін ол не тым суық, не жайлы, не тым ыстық. JOI-кун температураның күрт өзгеруіне төзе алмайтындықтан, тым суық бөлмеден соңғы рет шыққаннан кейін $X$ минуттан аз уақыт ішінде тым ыстық бөлмеге кіре алмайды. Дәл сол сияқты, тым ыстық бөлмеден соңғы рет шыққаннан кейін $X$ минуттан аз уақыт ішінде тым суық бөлмеге кіре алмайды.

Қозғалыс кезінде JOI-кун бөлмеге кірген бойда одан бірден шығуы тиіс. Сонымен қатар, ол дәліздің ортасынан кері бұрыла алмайды және $i$-ші дәлізбен өтуге $D_i$ минуттан артық уақыт жұмсай алмайды. Дегенмен, бұрын болған бөлмеге қайта кіруге және бұрын жүрген дәлізді қайта пайдалануға рұқсат етіледі.

Қазір JOI-кун $1$-ші бөлмеде тұр. Бұл бөлме JOI-кун үшін тым суық. JOI-кун зәулім үйдің шығар есігі орналасқан $N$-ші бөлмеге кірген сәтте үйден қашып шыға алады.

JOI-кунның зәулім үйден қашып шығуына кететін ең қысқа уақытты табыңыз.

Кіріс деректер

Кіріс деректер $1 + N + M$ жолдан тұрады.

$1$-ші жолда бос орын арқылы бөлінген $3$ бүтін сан $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) жазылған. Бұл зәулім үйде $N$ бөлме мен $M$ дәліз бар екенін және JOI-кунның температура өзгерісіне бейімделуіне $X$ минут кететінін білдіреді.

Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) $i$-ші бөлменің температурасын білдіретін $T_i$ ($0 \le T_i \le 2$) бүтін саны жазылған. JOI-кун үшін $i$-ші бөлме $T_i = 0$ болғанда тым суық, $T_i = 1$ болғанда жайлы, ал $T_i = 2$ болғанда тым ыстық болады. $T_1 = 0$ екеніне кепілдік беріледі.

Келесі $M$ жолдың $j$-ші жолында ($1 \le j \le M$) бос орын арқылы бөлінген $3$ бүтін сан $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) жазылған. Бұл $j$-ші дәліз $A_j$ бөлмесі мен $B_j$ бөлмесін жалғайтынын және онымен өтуге $D_j$ минут кететінін білдіреді. Бірдей бөлмелер жұбын жалғайтын бірнеше дәліз болуы мүмкін екеніне назар аударыңыз.

Берілген кіріс деректерде JOI-кунның зәулім үйден қашып шыға алатынына кепілдік беріледі.

Шығыс деректер

JOI-кунның зәулім үйден қашып шығуына ең кемі неше минут кететінін білдіретін бүтін санды $1$ жолда шығарыңыз.

Кіріс және шығыс мысалдары

Кіріс мысалы 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

Шығыс мысалы 1

9

Кіріс мысалы 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

Шығыс мысалы 2

6

1-кіріс мысалында бөлмелермен $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ ретімен жүріп өту ең қысқа жол болады.

2-кіріс мысалында кейбір бөлмелер жұбын (мысалы, $1$-ші бөлме мен $5$-ші бөлмені) жалғайтын бірнеше дәліз бар.