Deskripsi Masalah

JOI-kun si ular tersesat masuk ke dalam sebuah rumah besar. Sebelum ketahuan oleh penghuni rumah tersebut, ia harus melarikan diri dari sana.

Di rumah besar ini terdapat $N$ ruangan yang diberi nomor $1, 2, \dots, N$. Selain itu, terdapat $M$ koridor, di mana koridor ke-$i$ ($1 \le i \le M$) menghubungkan ruangan $A_i$ dan ruangan $B_i$. JOI-kun dapat melewati koridor-koridor ini ke dua arah, dan dibutuhkan waktu $D_i$ menit untuk melewati koridor $i$. Tidak ada cara lain untuk berpindah antarruangan selain melewati koridor.

Suhu setiap ruangan di rumah besar ini diatur secara konstan; bagi JOI-kun suhunya bisa terlalu dingin, nyaman, atau terlalu panas. Karena JOI-kun tidak tahan terhadap perubahan suhu yang mendadak, ia tidak dapat memasuki ruangan yang terlalu panas dalam waktu kurang dari $X$ menit sejak terakhir kali meninggalkan ruangan yang terlalu dingin. Demikian pula, ia tidak dapat memasuki ruangan yang terlalu dingin dalam waktu kurang dari $X$ menit sejak terakhir kali meninggalkan ruangan yang terlalu panas.

Saat bergerak, begitu memasuki sebuah ruangan, JOI-kun harus segera keluar dari ruangan tersebut. Selain itu, ia tidak dapat berbalik arah di tengah koridor maupun menghabiskan waktu lebih dari $D_i$ menit untuk melewati koridor $i$. Namun, ia diperbolehkan memasuki kembali ruangan yang sudah pernah dikunjungi atau menggunakan kembali koridor yang sudah pernah dilewati.

Saat ini JOI-kun berada di ruangan $1$. Ruangan ini terlalu dingin bagi JOI-kun. JOI-kun dapat melarikan diri dari rumah besar tersebut begitu ia memasuki ruangan $N$ tempat pintu keluar berada.

Carilah waktu tersingkat yang diperlukan JOI-kun untuk melarikan diri dari rumah besar tersebut.

Format Masukan

Masukan terdiri dari $1 + N + M$ baris.

Pada baris ke-$1$, tertulis $3$ bilangan bulat $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$) yang dipisahkan oleh spasi. Hal ini menyatakan bahwa terdapat $N$ ruangan dan $M$ koridor di rumah besar tersebut, serta JOI-kun memerlukan waktu $X$ menit untuk beradaptasi terhadap perubahan suhu.

Pada baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya, tertulis sebuah bilangan bulat $T_i$ ($0 \le T_i \le 2$) yang menyatakan suhu ruangan $i$. Bagi JOI-kun, ruangan $i$ terlalu dingin ketika $T_i = 0$, nyaman ketika $T_i = 1$, dan terlalu panas ketika $T_i = 2$. Dijamin bahwa $T_1 = 0$.

Pada baris ke-$j$ ($1 \le j \le M$) dari $M$ baris berikutnya, tertulis $3$ bilangan bulat $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$) yang dipisahkan oleh spasi. Hal ini menyatakan bahwa koridor $j$ menghubungkan ruangan $A_j$ dan ruangan $B_j$, serta membutuhkan waktu $D_j$ menit untuk dilewati. Perhatikan bahwa mungkin terdapat lebih dari satu koridor yang menghubungkan pasangan ruangan yang sama.

Pada data masukan yang diberikan, dijamin bahwa JOI-kun dapat melarikan diri dari rumah besar tersebut.

Format Keluaran

Keluarkan dalam $1$ baris sebuah bilangan bulat yang menyatakan waktu minimum dalam menit yang diperlukan JOI-kun untuk melarikan diri dari rumah besar tersebut.

Contoh Masukan dan Keluaran

Contoh Masukan 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

Contoh Keluaran 1

9

Contoh Masukan 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

Contoh Keluaran 2

6

Pada Contoh Masukan 1, berpindah melewati ruangan dengan urutan $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$ adalah yang paling singkat.

Pada Contoh Masukan 2, terdapat beberapa koridor yang menghubungkan pasangan ruangan yang sama (misalnya ruangan $1$ dan ruangan $5$).