Byteland consists of N houses numbered 1..N. The house i has K[i] members living in it. There are also M roads connecting some pairs of houses. The roads are all bidirectional and each road has a certain length. There is a candy shop located in house S.

The citizens of Byteland decide to send candies to each other's houses (not to their own of-course). The amount of candies sent by house u to house v should be K[v] (one for each member of house v). The owner of the candy shop, being a shrewd businessman, decides the following :
A delivery from u to v must necessarily pass through the candy shop, and it's cost will be the length of the shortest such path.
Each candy shall be delivered independently, so the delivery from u to v will cost K[v] times the length of the shortest path from u to v through the candy shop.

Input

The first line contains three integers N, M, and S.

The next line contains N integers, denoting the K[] values of the houses.

The next M lines contain three integers each: u, v, w, denoting that there is a road of length w connecting house u and v.

Output

Print N space separated integers in the same line, where the ith value is the total cost incurred by house i.

Constraints

1 ≤ N, M ≤ 100,000

0 ≤ w ≤ 100000

1 ≤ K[i] ≤ 100

1 ≤ u, v, S ≤ N

Note: There may be certain families who are unable to send candies to each other due to inadequate road connectivity. These incur 0 cost.

SAMPLE INPUT
5 4 3
5 4 3 2 1
1 2 5
3 2 3
3 5 1
1 5 1

SAMPLE OUTPUT
29 38 23 0 34

Explanation

The candy shop is at distance [2, 3, 0, inf, and 1] from houses 1, 2, 3, 4, and 5 respectively.

House 1 delivers candies to houses 2, 3, 5 at costs 4 * 5 + 3 * 2 + 1 * 3 = 29. It does not deliver to house 4.

House 4 is not connected to the candy shop, so it incurs 0 cost.

见题面

见题面