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