Maximum Coin Collection

Perry is exploring a collection of n islands connected by m sea routes. Each route is a directed edge connecting two islands: from island \(a_i\) to island \(b_i\) with a travel cost of \(c_i\) coins. Each island \(i\) has a treasure chest containing \(v_i\) coins. When Perry visits an island, he picks up the coins in its treasure chest. In particular, if he starts at island \(X\), he collects \(v_X\) immediately, and every time he travels from an island \(u\) to an island \(v\) (costing \(c\) coins), he gains an additional \(v_v\) coins upon arriving, incurring the travel cost.

He intends to finish his journey at a fixed destination island \(Y\). However, Perry is not sure which island he is currently on. Therefore, for every possible starting island \(X = 1,2,\dots,n\), he wants to know the maximum net coins he can collect by choosing an optimal journey from \(X\) to \(Y\>.

The net profit (or net coins) of a journey is defined as:

[ \text{profit} = \sum_{\text{island } i \text{ on the path}} v_i ; - ; \sum_{\text{each traversed edge } (u,v)} c(u,v). ]

Note: If there exists a cycle along the journey that can be exploited to accumulate an arbitrarily large number of coins (i.e. a positive cycle that is reachable from \(X\) and from which \(Y\) is reachable), then the answer for that starting island is -1. It is guaranteed that all coin values \(v_i\) and travel costs \(c_i\) are integers. You may assume that if a path from \(X\) to \(Y\) exists then the optimal journey will collect at least \(v_Y\) coins (by simply ending at \(Y\) without traversing any route).

inputFormat

The first line contains three integers \(n\), \(m\) and \(Y\) \((1 \leq n \leq 1000,\; 1 \leq m \leq 10000)\): the number of islands, the number of sea routes and the fixed destination island respectively.

The following \(m\) lines each contain three integers \(a_i\), \(b_i\) and \(c_i\) \((1 \leq a_i, b_i \leq n, \; c_i \ge 0)\), representing a directed sea route from island \(a_i\) to island \(b_i\) with cost \(c_i\) coins.

The last line contains \(n\) integers \(v_1, v_2, \dots, v_n\) \((v_i \ge 0)\) where \(v_i\) is the coin value in the treasure chest on island \(i\).

outputFormat

Output \(n\) lines. The \(i\)-th line should contain the maximum net coins that can be collected by starting at island \(i\) and ending at island \(Y\). If the profit can be made arbitrarily large (i.e. if a positive cycle is reachable on the path from \(i\) to \(Y\)), output -1 for that island. If island \(Y\) is not reachable from island \(i\), output gg (without quotes).

sample

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

10
9
7