Little C likes mountain climbing, but his physical stamina is average, and he cannot climb too high continuously. Today, Little C decides to climb Bit Peak. There are $n$ scenic spots on Bit Peak, and the altitude of the $i$-th spot is $h_i$ meters. There are $m$ bidirectional paths between the spots. The $i$-th path connects spot $u_i$ and spot $v_i$, and it takes $t_i$ minutes for Little C to traverse the $i$-th path in either direction. Little C accumulates fatigue while climbing. His initial fatigue is $0$, and the maximum fatigue he can tolerate is $H$. Suppose Little C is currently at spot $x$, and there is a path from spot $x$ to spot $y$: If the altitude of spot $x$ is higher than that of spot $y$, this is an easy downhill path. If Little C chooses to take this path, his stamina is restored, and his fatigue is reset to $0$. Otherwise, if Little C chooses to take this path, his fatigue increases by $h_y - h_x$. Little C can only take this path if his accumulated fatigue does not exceed $H$.

Now, Little C starts from spot $1$ and can only move between spots using these paths. For each spot, Little C wants to know the minimum time in minutes required to reach it, or if it is impossible to reach.

Input

The first line contains three positive integers $n, m, H$ ($2 \le n \le 10^4, 0 \le m \le 2 \times 10^4, 1 \le H \le 100$), representing the number of spots, the number of paths, and the maximum fatigue Little C can tolerate, respectively. The second line contains $n$ positive integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), representing the altitude of each spot. The next $m$ lines each contain three positive integers $u_i, v_i, t_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le t_i \le 10^9$), representing the two spots connected by a path and the time required to traverse it.

Output

Output a single line containing $n-1$ integers. The $i$-th integer represents the minimum time (in minutes) required for Little C to reach the $(i+1)$-th spot. If Little C can never reach that spot, output $-1$.

Examples

Input 1

6 7 3
1 2 3 4 5 6
1 2 1
2 4 10
1 3 8
2 3 2
3 5 9
4 3 100
2 6 2

Output 1

1 3 11 16 -1