哈尔滨有 $n$ 个公交车站，由 $m$ 条双向公路连接。无论身处何地，总能通过这些公路到达任意公交车站。这些公交车站编号为 $1, 2, \dots, n$。

如果你想从第 $i$ 个车站乘车前往第 $j$ 个车站（$1 \le i, j \le n$），你需要先为你的行程购买一张车票，然后进入相应的公交车。司机总是会选择通往目的地的最短路线，即包含公路数量最少的路线。但如果你的目的地太远，你将无法购买此类车票。具体来说，仅当你身处第 $i$ 个车站且 $dis(i, j) \le f_i$ 时，你才能购买从第 $i$ 个车站到第 $j$ 个车站的车票，其中 $dis(i, j)$ 表示 $i$ 和 $j$ 之间最短路线上的公路数量。

爱丽丝（Alice）目前在第一个车站，她希望去拜访她的好朋友鲍勃（Bob），鲍勃在第 $k$ 个（$1 \le k \le n$）车站。她需要乘坐几趟公交车，并在一天内到达第 $k$ 个车站。最初，在第 $i$ 个车站购买车票的费用为 $c_i$ 美元。在第二天购买车票的费用为 $c_i + w_i$ 美元。如果她想在第三天购买车票，则需要支付 $c_i + 2w_i$ 美元，以此类推。简而言之，费用每天变化 $w_i$。

为了省钱，爱丽丝需要选择最佳日期 $T$（$1 \le T \le T_{\max}$），并在该天乘坐多趟公交车到达第 $k$ 个车站，使得车票总费用最小。注意，最初 $T = 1$，因此她在第 $T$ 天需要支付 $c_i + (T - 1)w_i$ 美元。

鲍勃还没有告诉爱丽丝他在哪里。请编写一个程序，帮助爱丽丝计算所有可能目的地 $k = 1, 2, \dots, n$ 的最便宜方案。

输入格式

输入仅包含一组测试数据。

第一行包含三个整数 $n, m$ 和 $T_{\max}$（$1 \le n \le 200\,000$，$n - 1 \le m \le n + 50$，$1 \le T_{\max} \le 10^6$），分别表示公交车站数量、公路数量和参数 $T_{\max}$。

接下来的 $n$ 行，每行包含三个整数 $f_i, c_i$ 和 $w_i$（$1 \le i \le n$，$1 \le f_i \le n$，$1 \le c_i \le 10^9$，$|w_i| \le 10^9$），表示第 $i$ 个公交车站的参数。保证每张车票的费用永远不会为负，且永远不会超过 $2 \cdot 10^9$。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le i \le m$，$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示连接第 $u_i$ 个车站和第 $v_i$ 个车站的双向公路。保证无论身处何地，总能通过这些公路到达任意公交车站。注意，同一对公交车站之间可能存在多条公路。

输出格式

输出 $n$ 行，其中第 $k$ 行（$1 \le k \le n$）包含一个整数，表示如果鲍勃在第 $k$ 个车站，爱丽丝需要支付的最小美元数。

样例

输入 1

6 6 2
1 50 -40
1 2 100
2 1 100
2 4 100
3 1 100
1 1 100
1 2
2 3
3 4
4 2
2 5
6 1

输出 1

0
10
52
52
52
10

说明

在样例测试中：

• 当 $k = 1$ 时，答案显然为 $0$。
• 当 $k = 2$ 时，最佳日期 $T$ 为 $2$。
• 当 $k = 3$ 时，最佳日期 $T$ 为 $1$。
• 当 $k = 4$ 时，最佳日期 $T$ 为 $1$。
• 当 $k = 5$ 时，最佳日期 $T$ 为 $1$。
• 当 $k = 6$ 时，最佳日期 $T$ 为 $2$。