给定一个包含 $n$ 个顶点和 $m$ 条边的图。每个顶点的编号为 $1$ 到 $n$。 每条边 $i$ 都有其权值 $w_i$，其中一些边是普通边，另一些是特殊边。 当你通过一条特殊边后，在通过该边后的下一步，你可以到达图中的任意顶点。如果你前往当前顶点通过原边 $i$ 可以到达的顶点，则代价变为 $w_i - K$（前提是 $0 \le w_i - K$，且你使用了边 $i$）；否则，代价变为 $0$（针对除原边可到达顶点之外的每个顶点）。 原边包括所有的普通边和特殊边。 现在你从 $S$ 出发，你需要计算从起点到每个顶点的最小代价（如果存在无法到达的情况，请输出 $-1$）。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$。接下来是测试用例的描述。 每个测试用例的第一行包含四个整数 $n, m, S, K$。 接下来的 $m$ 行，每行包含四个整数 $x, y, w, t$，表示一条连接 $x$ 和 $y$ 的有向边，权值为 $w$。$t = 0$ 表示它是普通边，$t = 1$ 表示它是特殊边。 $1 \le \sum m, \sum n \le 10^6$，$1 \le x, y, S \le n$，$1 \le w, K \le 10^9$。 $K \le w_i (1 \le i \le m)$。

输出格式

对于每个测试用例，在一行中打印 $n$ 个整数，即问题的答案。每行末尾有一个空格。如果无法到达，请输出 $-1$。

样例

输入 1

2
5 4 1 1
1 2 4 0
1 3 5 0
3 4 3 1
4 5 3 0
5 3 1 1
1 2 4 0
1 3 5 0
3 4 3 1

输出 1

0 4 5 8 10 
0 4 5 8 8