题目背景

（咯咯咯……）谁家的只因，拐了（一定是_FJ_拐的）！

题目描述

只因住在 $T$ 市，而只因现在在 $S$ 市，只因的妈妈还在等只因回来吃饭，请帮他规划还需几分钟到家。 有 $N$ 个城市，之间有 $M$ 条公路相连，公路之间是双向连接的，其中有些是高速公路。 只因很着急，不愿在 $S$ 市多呆。 高速公路每 $K$ 分钟两端城市会有大巴，这些大巴可以让只因比原来快 $50 \%$ 到达另一个城市（第一辆在时刻 $0$ 出发），如果不搭乘，则需花费原时间。 出发前只因突然得知每条高速公路的大巴都需花费 $x$ 元，可只因只有 $C$ 元，只因手足无措……

输入格式

第 $1$ 行输入四个非负整数，$N$，$M$，$K$，$C$。

第 $2$ 到第 $M+1$ 行，每行四个整数 $u$，$v$，$w$，$z$，表示 $u$ 市和 $v$ 市间有一条公路连接，需要 $w$ 分钟通过。如果 $z=1$ ，表示这条公路是高速公路，否则$z=0$。接下再输入一个整数 $x$，表示乘坐大巴的价钱（如果为高速公路，保证 $w$ 为偶数）。

最后一行两个整数，为题目描述的 $S$ 和 $T$。

输出格式

输出一个整数，表示只因回家的最少时间。如果不能到达，输出 $-1$。

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

4

3 3 3 1
3 1 8 1 2
1 2 4 0
2 3 1 0
1 3

5

数据规模与约定

数据范围

对于 $100\%$ 的数据，保证 $N\leqslant10^4$，$M\leqslant10^6$，$K\leqslant15$，$C\leqslant500$， $1 \leqslant u,v \leqslant N$， $w \leqslant 1000$，$0 \leqslant z \leqslant 1$，$x \leqslant 10^4$。保证无重边和自环。

注：要用快读，不然会TLE

快读代码：

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}