题目描述

在 3025 年，人类已经掌握了虫洞技术，并占领了 $n$ 个星球。为了连接这些星球，人类在星球之间建造了 $m$ 条虫洞。保证 $n$ 个星球之间互相连通。由于虫洞的开销巨大，所以保证 $m\leq n+40$。

Bessie 计划在这些星球之间进行旅行。她将会通过最近新开业的 FJ 交通公司以在各个星球之间来往。FJ 公司在每个星球都有去往其它星球的航班，通过第 $i$ 个星球的航班可以直接到达和该星球的最短距离不超过 $f_i$ 的星球。在开业的第一天，乘坐一次第 $i$ 个星球的航班需要花费 $c_i$ 元。

Bessie 现在在 $1$ 号星球，她想要去往某一个星球进行旅行。但是她还没有计划好去哪个星球旅行，所以请你计算对于每个星球（包括 $1$ 号星球），Bessie 到达该星球的最小花费。

输入格式

第一行三个整数，表示 $n,m,t$。

后面 $n$ 行，每行三个整数，表示 $f_i,c_i,w_i$。

后面 $m$ 行，每行两个整数 $u_i,v_i$，表示存在一条连接星球 $u_i$ 和 $v_i$ 的虫洞。

输出格式

$n$ 行，每行一个整数，表示到达每个星球的最小花费。

样例

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

0
10
12
12
12
10

数据范围

本题共 $25$ 个测试点，具体限制如下：

对于所有数据，$1\leq n\leq 2\times 10^5,n-1\leq m\leq n+40,1\leq f_i\leq n,1\leq c_i\leq 10^9$。输入的图连通，但不保证是简单图。