Rebellion of robots

题目描述

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.

样例

输入

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

输出

4