题目描述

下水道的主干路由 $n$ 个节点和 $n-1$ 条边组成，每条边有一个通过它所需的时间 $T_i$。换言之，这是一棵有 $n$ 个节点的带权树。现在，要用最快的速度赶往目标节点 $k$。下水道有一些塌陷，这导致主干路的某一段路径可以通过该塌陷到达另一条路径。对于一个塌陷，我们用 $(L_1, R_1, L_2, R_2, c)$ 来描述，即对于主干路上 $L_1$ 到 $R_1$ 路径上的任意节点 $x$，和 $L_2$ 到 $R_2$ 路径上的任意节点 $y$，都可以在 $c$ 的时间内从 $x$ 走到 $y$。由于无法确定自己所在的节点，因此需要计算每个节点到目标节点 $k$ 的最短距离。注意，树边是双向边，所有边都是单向的。

输入格式

第一行包含三个整数 $n, m, k$，分别表示节点数、塌陷数和目标节点编号，空格分隔。

接下来 $n-1$ 行，每行包含三个整数 $x, y, t$，表示主干路的一条边，连接节点 $x$ 和节点 $y$，通过这条边的时间为 $t$。

接下来 $m$ 行，每行包含五个整数 $L_1, R_1, L_2, R_2, c$，表示一个塌陷。通过该塌陷，可以在时间 $c$ 内从主干路上 $L_1$ 到 $R_1$ 之间的任意节点 $x$，走到 $L_2$ 到 $R_2$ 之间的任意节点 $y$。

约束条件：

• $n \leq 250000$
• $m \leq 100000$
• $1 \leq L_1, L_2, R_1, R_2, x, y \leq n$
• $1 \leq t, c \leq 2^{31}-1$

输出格式

输出 $n$ 行，每行一个整数，表示第 $i$ 个节点到第 $k$ 个节点的最短路径长度。特别地，在第 $k$ 行应当输出 $0$。

输入数据示例

5 3 5
1 2 100
2 3 100
3 4 100
4 5 100
1 2 4 5 200
2 2 4 4 90
3 3 2 2 5

200
190
195
100
0

样例解释

• 第 1 个节点到目标节点 5 的最短路径经过塌陷，路径长度为 200。
• 第 2 个节点通过塌陷后的最短路径长度为 190。
• 第 3 个节点通过塌陷后的最短路径长度为 195。
• 第 4 个节点与目标节点直接相连，路径长度为 100。
• 第 5 个节点就是目标节点，路径长度为 0。