Location, Location, Location

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 3.0 seconds

Everybody knows that location is very important in business. Up to now, you have only had 1 shop. However, having profited from an excellent choice of location for your first branch, you are fortunate enough to be able to open two more branches in the city.

Your objective is to find two locations to open up new branches so that the average time it takes somebody to get to the closest branch is minimized.

In total, the city has $N$ intersections (numbered $1$ to $N$ ), around which a cluster of apartments are built. The intersections are connected by $M$ roads, which each take some time to travel. No time is required to get from an apartment to the intersection where it is located. Your current branch is located at intersection $X$ . You must find two new locations at intersections $Y$ and $Z$ so that the average travel time of everybody to their closest branch is minimised. There is at most 1 road between any pair of intersections, and it is guaranteed that there is a path between every pair of intersections.

Input

The first line contains three integers, $N$ ( $3 \leq N \leq 400$ ), $M$ ( $M \leq 100,000$ ) and $X$ (the location of your current branch, $1 \leq X \leq N$ ).

On the second line are $N$ integers, $k_1 k_2 ... k_N$ where $0 \leq k_i \leq 10,000$ represents the number of people living in the apartments at intersection $i$ .

Each of the next $M$ lines describe a road, which can be travelled in both directions. Each line contains 3 integers, $A_j$ , $B_j$ and $C_j$ describing a road between intersections $A_j$ and $B_j$ , taking $C_j$ seconds ( $1 \leq C_i \leq 10,000$ ).

Output

On a single line, output two integers $Y$ and $Z$ - the best location to place the new branches.

If there are multiple pairs of locations with the same average minimum time, output any pair of locations. The two integers can be output in any order.

Subtasks

Subtask 1 (20%): $N \leq 40$
Subtask 2 (20%): $C_j = 1$ for all $j$
Subtask 3 (20%): $k_i = 1$ for all $i$
Subtask 4 (20%): $M = N-1$
Subtask 5 (20%): No further restrictions apply.

Explanation

For the first sample case, new branches are opened at intersections 2 and 3, so only the 4th intersection is without a branch. It takes 9 seconds for those 2 residents to get to the branch at intersection 1. The average travelling time of the 12 residents in the city is $\frac{2 \times 9}{12} = 1.5$ . This is the smallest possible.

Sample Input 1

Sample Output 1

2 3

Sample Input 2

6 5 1
5 3 1 6 6 7
4 6 1
2 3 1
1 4 3
6 3 1
3 5 2

Sample Output 2

5 6

Sample Input 3

6 8 1
1 1 1 1 1 1
2 5 1
1 5 1
4 3 1
1 6 1
5 6 1
6 3 1
2 1 1
1 3 1

Sample Output 3

2 3