Delivering Candies

4.1

60 votes
Easy-Medium
Problem

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.

Time Limit: 2
Memory Limit: 256
Source Limit:
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.

Editor Image

?