11783: 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.

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