30124 - 背包

给定一个包含 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 行，每行包含三个整数 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 所需的最少背包数量。如果无法到达 T，输出 -1。