U453499 洛谷狂人日记 (eating)

从前有个腐朽的洛谷，@username 是其中的一员，今天他要进食后人。只见 @username 发布了一个帖子，到处都歪歪斜斜地写着什么“不开long long见祖宗”“多测不清空”之类的难懂的话，但是仔细一看，字里行间都写着“吃人”。

在一个讨论区中有 $n$ 个后人。@username 的当前位置是 $0$。 第 $i$ 个后人的位置是 $i$，它的美味值是 $b_i$。 洛谷世界有着奇怪的地图。地图包含 $m$ 条双向道路，第 $i$ 条路的长度为 $l_i$。 @username 不想走太多路，但是又想吃到好吃的后人。所以 @username 最多只会移动 $c$ 的距离。@username 可以重复经过某个点或者某条边。 @username 想要求出，他最多能吃到多少美味值的后人。 需要注意的是，由于那些“不开long long见祖宗”的警示，蒙骗了这些后人，因此你需要处理 $q$ 个询问，对于每个询问，会更改第 $i$ 个后人的 $b_i$ 值。

输入的第一行是 $5$ 个整数 $n,m,c,q$。 接下来 $n$ 行，每行 $2$ 个整数，第 $(i+1)$ 行的整数表示 $a_i$ 和 $b_i$。 接下来 $m$ 行，每行 $3$ 个整数，第 $(i+n+1)$ 行的整数依次为 $u_i, v_i, l_i$， 表示有一条从 $u_i$ 到 $v_i$ ， 长为 $l_i$ 的双向道路。 接下来 $q$ 行，表示一个询问： $1\ i\ j $ 表示将 $b_i$ 修改为 $j$。 $2$ 表示查询 @username 最多能吃到的美味值。

对于每个询问，输出答案。

提醒大家，警示后人就好好警示，不要再进食了，否则洛谷将会臭名昭著。~~能不能去吃线段树、平衡树、字典树、主席树、map......~~ $0 \le u_i,v_i \le n \le 10^5, 0 \le q \le 10^5, 0 \le m \le 10^6,0 \le b_i \le 10^9,0 \le c,l_i \le 10^{18}$