사이버랜드

3742년이 되었고, 이제 사이버랜드가 APIO를 개최할 차례이다. 이 세계에는 $0$부터 $N - 1$까지 번호가 붙은 나라 $N$개와, $0$부터 $M - 1$까지 번호가 붙은 양방향 도로 $M$개가 있다. $i$번째 도로($0 \le i < M$)는 서로 다른 두 나라 $x[i]$와 $y[i]$를 잇고, 이 도로를 지나는 데 $c[i]$만큼의 시간이 걸린다. 자국을 제외한 모든 참가자는 APIO를 위해 사이버랜드에 모였다. 당신은 나라 $0$에 살고 있고, 사이버랜드는 나라 $H$이다. 자국에서 가장 똑똑한 사람으로서 당신의 도움이 다시 한번 시급히 필요하다. 구체적으로, 자국에서 사이버랜드에 도착하는 데 필요한 최소 시간을 구하라. 어떤 나라에서는 총 통과 시간을 $0$으로 만들 수 있다. 또 어떤 나라에서는 총 통과 시간을 $2$로 나눌 수 있다(2로 나누기 능력). 같은 나라를 여러 번 방문해도 된다. 나라를 방문할 때마다 그 나라의 특수 능력을 쓸지 말지 선택할 수 있다. 다만 한 번의 방문에서 특수 능력은 최대 한 번만 쓸 수 있다(따라서 나라를 여러 번 방문하면 특수 능력도 여러 번 쓸 수 있다). 더불어 2로 나누기 능력은 사이버랜드 화학재단에 적발되지 않도록 최대 $K$번까지만 쓸 수 있다. 사이버랜드에 도착하면 곧 열릴 대 APIO 대회 때문에 더 이상 어디로도 이동할 수 없다. 배열 $arr$이 주어지며, $arr_i$($0 \le i < N$)는 나라 $i$의 특수 능력을 나타낸다. 특수 능력은 세 종류이다. $arr_i = 0$이면 그 나라에서 통과 시간을 $0$으로 만든다. $arr_i = 1$이면 그 나라에서 통과 시간이 변하지 않는다. $arr_i = 2$이면 그 나라에서 통과 시간을 $2$로 나눈다. $arr_0 = arr_H = 1$임이 보장된다. 즉 사이버랜드와 자국에는 특수 능력이 없다. 자국은 APIO의 순간순간을 놓치고 싶지 않으므로, 사이버랜드에 도착하는 최소 시간을 구하라. 사이버랜드에 도달할 수 없다면 답은 $-1$이다.

$2 \le N \le 10^5$, $\sum N \le 10^5$. $0 \le M \le \min\{10^5, \frac{N(N-1)}{2}\}$, $\sum M \le 10^5$. $1 \le K \le 10^6$. $1 \le H < N$. $0 \le x[i], y[i] < N$, $x[i] \ne y[i]$. $1 \le c[i] \le 10^9$. $arr[i] \in \{0, 1, 2\}$. 두 나라를 잇는 도로는 최대 하나뿐임이 보장된다.