신호등

다익스트라 알고리즘은 음수 가중치를 갖는 변이 없는 그래프에서 출발점과 도착점 사이의 최단 경로를 구한다. 꼭짓점이 교차로를 나타내고 변이 두 교차로를 잇는 도로의 길이를 나타내면, 두 교차로 사이의 최단 경로를 이 알고리즘으로 구할 수 있다.

그러나 실제 도로에는 교차로마다 신호등이 있어서 교차로를 언제나 지날 수 있는 것은 아니다. 그래서 최단 경로가 아닌 길로 우회하는 편이 목적지에 더 빨리 닿기도 한다.

신호등은 $P$초를 주기로 신호가 바뀐다. 교차로 $i$와 연결된 교차로의 번호를 $x_1 < x_2 < \cdots < x_n$이라 하자. 처음 $P$초 동안은 $x_1$에서 온 차만 $i$를 거쳐 $x_2, \ldots, x_n$으로 갈 수 있고, 그다음 $P$초 동안은 $x_2$에서 온 차만 $i$를 거쳐 $x_1, x_3, \ldots, x_n$으로 갈 수 있다. 이렇게 교차로 번호가 작은 쪽부터 $P$초씩 차례로 $i$를 지날 권한을 얻고, $n \times P$초가 지나면 다시 $x_1$ 차례로 돌아온다. $x_k$에서 온 차는 $x_k$를 뺀 나머지 교차로로만 갈 수 있다.

(a)	(b)	(c)

예를 들어 교차로 3번과 연결된 교차로가 1번, 4번, 5번이면, 0초 이상 $P$초 미만에는 그림 (a)처럼 1번 교차로에서 온 차가 3번 교차로를 거쳐 다른 교차로로 갈 수 있다. $P$초 이상 $2P$초 미만에는 그림 (b)처럼 4번 교차로에서 온 차가 갈 수 있고, $2P$초 이상 $3P$초 미만에는 그림 (c)처럼 5번 교차로에서 온 차가 1번이나 4번 교차로로 갈 수 있다. $3P$초 이상 $4P$초 미만에는 다시 (a)와 같은 상태가 된다.

다음 조건에서 자동차가 출발 교차로에서 도착 교차로까지 가는 최소 시간을 구한다.

• 자동차는 1초에 길이 1만큼 이동한다.
• 출발지와 목적지는 모두 교차로다.
• 모든 신호등은 자동차가 출발하는 순간에 함께 동작을 시작한다.
• 출발 교차로와 도착 교차로에서는 신호를 기다리지 않는다.
• 어떤 교차로에서 같은 교차로로 돌아오는 도로는 없다.

예를 들어 위 도로망에서 출발 교차로가 1번이고 도착 교차로가 4번이라 하자. 1번 교차로에서 출발한 차는 10초에 3번 교차로에 도착한다. 3번 교차로의 주기가 2초라면 10초 이상 12초 미만에는 5번 교차로에서 온 차만 도로를 이용할 수 있으므로, 1번 교차로에서 온 차는 12초까지 기다려야 한다. 따라서 1번 교차로에서 4번 교차로까지 가는 데 14초가 걸린다.

모든 도로의 길이와 신호등 주기가 주어질 때, 출발 교차로에서 도착 교차로까지 가는 최소 시간을 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 교차로의 수 $N$ ($1 \le N \le 10^5$), 도로의 수 $M$ ($0 \le M \le 10^5$), 출발 교차로의 번호 $S$ ($1 \le S \le N$), 도착 교차로의 번호 $D$ ($1 \le D \le N$)가 주어진다.

이어지는 $M$개의 줄에는 $a$, $b$, $c$ ($1 \le a, b \le N$, $a \ne b$, $1 \le c \le 10^5$)가 주어진다. $a$번 교차로와 $b$번 교차로를 잇는 길이 $c$의 양방향 도로가 있다는 뜻이다.

그다음 줄에는 각 교차로의 신호등 주기 $P_1, P_2, \ldots, P_N$ ($1 \le P_i \le 100$)이 공백 하나로 구분되어 주어진다.

두 교차로 사이에 도로는 많아야 하나 있다.

각 테스트 케이스마다 출발 교차로에서 도착 교차로까지 가는 데 걸리는 최소 시간을 한 줄에 출력한다. 결과가 32비트 정수 범위를 넘을 수 있으므로 64비트 정수형을 쓰기를 권한다. 도착 교차로로 갈 수 있는 경로가 없으면 -1을 출력한다.