Traffic Lights

Dijkstra's algorithm finds a shortest path between a source and a target in a graph whose edges all have non-negative weights. If the vertices are intersections and each edge is the length of a road joining two intersections, the algorithm gives a shortest route between two intersections.

Real roads have a traffic light at every intersection, so a car cannot pass through an intersection whenever it likes. Taking a detour off the shortest route sometimes reaches the destination sooner.

A traffic light changes its signal every $P$ seconds. Let the intersections joined to intersection $i$ be numbered $x_1 < x_2 < \cdots < x_n$. During the first $P$ seconds only cars that came from $x_1$ may pass through $i$ toward $x_2, \ldots, x_n$, and during the next $P$ seconds only cars that came from $x_2$ may pass through $i$ toward $x_1, x_3, \ldots, x_n$. The right to pass through $i$ moves over the neighbours in increasing order of number, $P$ seconds each, and after $n \times P$ seconds it returns to $x_1$. A car that came from $x_k$ may leave toward any neighbour except $x_k$.

(a)	(b)	(c)

For example, suppose intersection 3 is joined to intersections 1, 4 and 5. From 0 seconds up to $P$ seconds, picture (a) applies and cars that reached intersection 3 over the road from intersection 1 may take a road to another intersection. From $P$ seconds up to $2P$ seconds, picture (b) applies and cars that came from intersection 4 may move on. From $2P$ seconds up to $3P$ seconds, picture (c) applies and cars that came from intersection 5 may go to intersection 1 or intersection 4. From $3P$ seconds up to $4P$ seconds the state of (a) returns.

Find the minimum time for a car to travel from its origin to its destination under these conditions.

• A car travels 1 unit of length per second.
• The origin and the destination are both intersections.
• Every traffic light starts working at the moment the car departs.
• The car waits for no signal at the origin intersection and at the destination intersection.
• No road leads from an intersection back to the same intersection.

For example, take the road network above with intersection 1 as the origin and intersection 4 as the destination. A car leaving intersection 1 reaches intersection 3 at second 10. If the period of intersection 3 is 2 seconds, then from second 10 up to second 12 only cars that came from intersection 5 may use the roads, so a car that came from intersection 1 waits until second 12. Driving from intersection 1 to intersection 4 therefore takes 14 seconds.

Given every road length and every signal period, find the minimum time to drive from the origin intersection to the destination intersection.

The first line has the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case has the number of intersections $N$ ($1 \le N \le 10^5$), the number of roads $M$ ($0 \le M \le 10^5$), the number of the origin intersection $S$ ($1 \le S \le N$) and the number of the destination intersection $D$ ($1 \le D \le N$).

Each of the next $M$ lines has $a$, $b$, $c$ ($1 \le a, b \le N$, $a \ne b$, $1 \le c \le 10^5$). It means that a two-way road of length $c$ joins intersection $a$ and intersection $b$.

The next line has the signal periods $P_1, P_2, \ldots, P_N$ ($1 \le P_i \le 100$) of the intersections, separated by single spaces.

At most one road joins any two intersections.

For each test case, print on its own line the minimum time to drive from the origin intersection to the destination intersection. The result can exceed the range of a 32-bit integer, so a 64-bit integer type is recommended. If no route reaches the destination intersection, print -1.