문제

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

소방차에는 물탱크가 있어서 이곳에 저장한 물을 화재를 진압하는데에 사용할 수 있다. 소방차는 물탱크가 빈 상태로 출발하지만, 이동 중에 교차로에 설치된 소화전을 이용해서 물탱크에 물을 충전할 수 있다. $i$번째 교차로에서 충전할 수 있는 물의 양은 $a_i$리터인데, 이를 초과해서 이용할 경우 $i$번째 교차로에 사는 주민들에게 피해를 줄 수 있다. 교차로에서 물을 충전하는데에는 시간이 걸리지 않고, 소방차의 물탱크의 용량에도 제한이 없다.

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

입력

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

둘째 줄에 정수 $a_1, a_2, ..., a_N$이 주어진다. $a_i(1 \le a_i \le 10\ 000)$는 $i$번째 교차로에서 충전할 수 있는 물의 양이다.

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

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

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

출력

소방차가 $S$번 교차로에서 $T$번 교차로까지 최단 경로로 이동하면서 동시에 최대한 많은 양의 물을 가지고 도착했을 때, 소방차의 이동 거리와 물탱크에 충전된 물의 양을 출력한다. 만약 소방차가 $T$번 교차로에 도착할 수 없다면 -1만을 출력한다.

예제 입력 1

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

예제 출력 1

5 17

$1→2→5→8$ 순으로 교차로를 방문하면 경로의 길이는 $5(1+3+1)$, 물탱크에 충전된 물의 양은 $17(7 + 2 + 5 + 3)$리터가 된다.

예제 입력 2

4
3 2 1 4
3
1 2 2
1 2 3
2 3 1
1 4

예제 출력 2

-1