Description

下水道的主干路由n个节点和n-l条边组成，每条边有一个通过它所需的时间Ti。换言之，这是一棵n个节点的带权

树。现在，要用最快的速度赶往目标节点k。下水道有一些塌陷，这导致主干路的某一段路径可以通过该塌陷到另

一条路径。对于一个塌陷，我们用(L1，ri，L2，R2，c)来描述，即对于主干路上L1到R1路径上的任意节点x，L2到

r2路径上的任意节点y，都可以在c的时间内从x走到y。因为不知道自己所在的到底是哪个节点，所以要求出每个节

点到目标节点K的最短距离。注意边是单向的

Format

Input

第一行两个数n，m，k，表示节点数、塌陷数和目标节点编号，空格分隔。

接下来n-l行，每行3个数x,y,t，表示主干路的一条边连接点x,y，通过的时间为t。

接下来m行，每行5个数L1，r1，L2，r2，c，表示一个塌陷。

N<=250000

m<=100000

1 < = L1,L2, R1, R2,x,y < = N

1< = t,c< = 2^31-1。

Output

n行，每行一个数，表示第i个节点到第k个节点的最短路径长度。

特别的，在第k行你应当输出0。

Samples

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