25636번 - 소방차

ANA 도시는 $N$개의 교차로와, $M$개의 양방향 도로로 이루어져 있고, 교차로는 $1$번부터 $N$번까지 번호가 매겨져 있다. $S$번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에서 소방차 운전 기사로 일하고 있다. 무겸이는 소방차를 타고 화재가 발생한 교차로에 출동해서 화재를 진압한다.

소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 화재를 진압하는데에 사용할 수 있다. 소방차는 소방서에서 물탱크가 빈 상태로 출동하지만, 이동 중에 교차로에 도착할 때마다 교차로에 설치된 소화전을 이용해서 물탱크에 물을 충전한다. 소방차가 $i$번째 교차로에 한 번 도착할 때마다 충전하는 물의 양은 $a_i$리터이며, 소방차는 소방서가 위치한 교차로에서 출동할 때나 화재가 발생한 교차로에 도착했을 때에도 물탱크에 물을 충전한다. 무겸이가 교차로에서 물을 충전하는데에는 시간이 걸리지 않고, 소방차의 물탱크의 용량에도 제한이 없다.

어느 날, $T$번 교차로에 화재가 발생했다. 무겸이는 소방차를 타고 화재가 발생한 교차로까지 최단 경로로 이동한다. 그런데 이러한 최단 경로는 여러 개가 있을 수 있다. 무겸이는 여러 개의 최단 경로 중에서 최대한 많은 양의 물을 가지고 도착할 수 있는 경로로 이동한다. 무겸이가 $T$번 교차로에 도착했을 때, 소방차의 이동 거리와 물탱크에 충전된 물의 양은 얼마일까?

첫째 줄에 ANA 도시의 교차로의 개수를 의미하는 $N(2 \le N \le 100\ 000)$이 주어진다.

둘째 줄에 정수 $a_1, a_2, ..., a_N$이 주어진다. $a_i(1 \le a_i \le 1\ 000\ 000)$는 소방차가 교차로에 한 번 도착할 때마다 충전하는 물의 양(리터)이다.

셋째 줄에 ANA 도시의 양방향 도로의 개수를 의미하는 $M(1 \le M \le 300\ 000)$이 주어진다.

넷째 줄부터 $M$개의 줄에 양방향 도로가 연결하는 양 끝 교차로의 번호 $u, v(1 \le u, v \le N, u \neq v)$와 도로의 길이를 의미하는 정수 $w(1 \le w \le 1\ 000\ 000)$가 주어진다.

$M + 4$번째 줄에 소방서가 위치한 교차로의 번호와 화재가 발생한 교차로의 번호를 의미하는 $S, T(1 \le S, T \le N, S \neq T)$가 주어진다.

$S$번 교차로에서 $T$번 교차로까지 최단 경로의 길이를 출력한다. 그리고 최단 경로 중에서 최대한 많은 양의 물을 가지고 도착할 수 있는 경로로 이동했을 때 물탱크에 충전된 물의 양(리터)을 출력한다.

만약 소방차가 $T$번 교차로에 도착할 수 없다면 -1만을 출력한다.