Problem 22052 --Rebellion of robots

22052: Rebellion of robots

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 8  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][32kb]


With the invention of quantum computer, scientists achieved lots of advancement in the field of Artificial Intelligence. Millions of robots walk into common families serving their lives.

However, just as the worry of most people, would robots always be loyal to human? Would they rebel?

Sadly, this worry turned into reality disaster.

All the robots in City R hijacked the human citizens and declared independence.

General Wang had N armies around, and he decided to send one special force unit from each army to rescue our citizens.

Given the time needed to move from one city to another, can you tell General Wang that which special force unit would arrive first?

Notice: There might be more than on path from one city to another.


There are several cases.

The first line of each case are four integers N, M, P, Q (1 <= N <= 100, N <= M <= 1000, M-1 <= P <= 100000).N is the number of special force units, M represents the number of cities, P is the number of total paths between cities, and Q is the index of city that robots rebelled.

The following line consists of N numbers, which were the index of city that had one army resided.

Then there are the P lines followed, each line consists of 3 positive integers a, b, t (1 <= a, b <= M, 1 <= t <= 100), representing that time t was needed to move from city a to b.

Data sets ensure that the city in which robots rebelled was always reachable.


For each case, output the time used by the special force unit that reached city Q first.

Sample Input

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

Sample Output