23493번 - Back and Forth 다국어

문제

There are $n$ stations and $m$ directed roads between them.

One day, Chiaki is going from the $s$-th station to the $t$-th station, then back to the $s$-th station. Doing so, he needs to buy tickets for stations he passes. The price the tickets for the $i$-th station is $p_i$. If Chiaki buys a ticket for the $i$-th station, he can passes the station as many times as he wants. Find the minimum price of tickets to buy.

입력

There are multiple test cases. The first line of the input contains an integer $T$ (1ドル \leq T \leq 200$) indicating the number of test cases. For each test case:

The first line of each test case contains four integers $n,ドル $m,ドル $s$ and $t$ (1ドル \leq n \leq 200,ドル 0ドル \leq m \leq n \times (n - 1),ドル 1ドル \leq s, t \leq n$). The second line contains $n$ integers $p_1, p_2, \dots, p_n$ (1ドル \leq p_i \leq 100$). The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i,ドル which denote a road from the $a_i$ station to the $b_i$-th station (1ドル \leq a_i, b_i \leq n$).

The sum of all $n$ does not exceed 200ドル$.

출력

For each test case, output an integer denoting the answer. Print $-1$ for no solution.

제한

힌트