Lake‐Bottom City Trip

You are given an undirected tree with n nodes and n – 1 edges. Each edge has an integer weight. In addition, you are given a positive integer p (called the lake number). Three friends (Yue, Ling, and Ying) explore the city. Initially, each of their counters is 0. Every time they traverse an edge with weight w, Yue’s and Ying’s counters are incremented by w, while Ling’s counter increases by 1. They are not allowed to visit any vertex more than once.

At any moment immediately after traversing an edge, if Ling’s counter is a multiple of p (i.e. if p divides the number of edges traversed since the last reset), Yue may perform an operation: subtract Ying’s counter’s value (which equals the sum of the weights on the edges traversed since the last reset) from her own counter, and then both Ling’s and Ying’s counters are reset to 0. Formally, we define an extension as follows. Suppose you are at vertex u with three counters a,b,c all initially 0 (where a is Yue’s counter, b counts the number of edges since the last reset, and c is the accumulated sum of weights in the current segment). When you extend from u along an edge (u, v, w) (which has weight w), update:

• u ← v,
• a ← a + w,
• b ← b + 1,
• c ← c + w.

Then, if p divides b (i.e. if the number of traversed edges since the last reset is a multiple of p), you may choose to perform the following operation:

• a ← a – c,
• b ← 0,
• c ← 0.

For a fixed starting vertex s and any other vertex v, let f(s,v) be the minimum possible final value of Yue’s counter upon reaching v by a simple path starting at s (i.e. never revisiting a vertex), if you make optimal choices on whether or not to perform the subtraction operation when available.

It turns out that if you analyze the optimal strategy along the unique simple path from s to v, the best decision is as follows. Suppose the simple path from s to v consists of a sequence of edges with weights w₁, w₂, …, w_L (with L being the number of edges). Let P(i) be the prefix sum: P(0) = 0 and P(i) = \(\sum_{j=1}^{i} w_j\) for 1 ≤ i ≤ L. Notice that after every complete block of p edges (i.e. when i is a multiple of p) you have the option to reset. The optimal strategy is to perform the reset if and only if the sum of the weights in that block is positive. Thus,

\[ f(s,v)=P(L)-\sum_{j=1}^{\lfloor L/p\rfloor}\max\Bigl\{P(j\cdot p)-P((j-1)\cdot p),0\Bigr\}. \]

You are also given a sequence of m starting vertices: s₁, s₂, …, s_m. For each vertex u (from 1 to n), compute

[ answer(u)=\min_{1\le i\le m} f(s_i,u). ]

Input Constraints:

• The first line contains three integers n, m and p.
• The second line contains m integers s₁, s₂, ..., s_m (1-indexed).
• Each of the next n - 1 lines contains three integers u, v and w representing an edge between nodes u and v with weight w.

Output: For each vertex from 1 to n, output the computed minimal value separated by spaces.

Note: The optimal strategy on a given simple path is to partition the path into segments of length exactly p and reset at those segments if the sum of that segment is positive; otherwise, keep accumulating. Use this observation to compute f(s,v) for each pair and then take the minimum over all given starting vertices.

inputFormat

The first line contains three integers n, m and p – the number of nodes, the number of starting vertices, and the lake number respectively.

The second line contains m integers s₁, s₂, ..., s_m (1-indexed).

Each of the next n – 1 lines contains three integers u, v and w meaning that there is an undirected edge between u and v with weight w.

outputFormat

Output a single line with n space‐separated integers. The i^th integer is the value \(\min_{1\le i\le m} f(s_i,i)\), i.e. the minimum possible value on Yue’s counter when reaching vertex i among all given starting vertices.

sample

5 2 2
1 3
1 2 3
2 3 -1
2 4 2
4 5 1

0 -1 0 0 1