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.