给定一个包含 $n$ 个顶点和 $m$ 条边的无向图，每条边上都有一个重量为 $w_i$ 的物品。小 S 有一个强迫症：每次他经过一条边时，他必须把该边上的物品放入他的背包中。背包的容量为 $V$。最初，他从一个新背包开始。如果当前背包的剩余容量不足以装下 $w_i$，他就会换一个新背包（并丢弃旧背包）。对于从 $1$ 到 $n$ 的每个起点，小 S 会选择一条路径以到达指定的顶点 $T$。你的任务是确定从每个起点出发到达 $T$ 所需的最少背包数量。如果无法到达 $T$，则输出 $-1$。

输入格式

第一行包含四个整数 $n$、$m$、$V$ 和 $T$（$1 \le n, m, V \le 10^5$，$1 \le T \le n$）。

接下来的 $m$ 行，每行包含三个整数；第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $w_i$，表示连接 $x_i$ 和 $y_i$ 的一条边，其上的物品重量为 $w_i$。保证 $1 \le x_i, y_i \le n$ 且 $1 \le w_i \le V$。

输出格式

输出单行，包含 $n$ 个整数；第 $i$ 个整数表示从顶点 $i$ 出发时所需的最少背包数量。如果无法到达 $T$，则输出 $-1$。

样例

样例输入 1

8 10 7 4
1 2 4
2 3 4
3 4 4
1 5 2
5 6 5
6 7 3
7 4 4
2 6 3
3 6 1
2 5 3

样例输出 1

2 2 1 1 2 1 1 -1