卯酉东海道
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

琪露诺想找三月精一起玩。她计划乘坐广重 36 号列车从雾之湖去到博丽神社。

整个隙间交通网络目前具有 n 个站台，但是由于需要收费，因而每个通道都是单向道路，同时每条通道具有一定的颜色和费用（冰块）。总的隙间通道一共有 m 条，总的通道颜色一共有 l 种。

琪露诺有一张通行卡，在她出发前，她可以任意染色该通行卡而不花费费用。当通行卡的颜色与琪露诺想要经过的通道颜色相同时，琪露诺就可以借助该通路到达下一站，花费这条道路的冰块数 w 。若通行卡的颜色与琪露诺想要经过的通道颜色不相同，琪露诺需要支付冰块数 base \times w ，同时将通行卡颜色改为该通道的颜色后，才可通过。

现在琪露诺在 1 号雾之湖站，要去 n 号博丽神社站。问在最优决策的情况下，琪露诺需要最少花费多少冰块。

输入描述:

输入的第一行包括三个正整数 n, m, l, base ，分别表示节点的个数、边的个数、所有通道的颜色种类数量，通行卡改变颜色时的费用倍率。

接下来 m 行，表示该隙间交通网络的总边数。每一行给出四个正整数 u, v, col, w ，表示一条从 u 到 v 、颜色为 col 、支付冰块数为 w 的有向边。

输出描述:

如果不存在任何方案，则输出一行一个整数 -1 。

否则输出整数，表示在最优决策下，琪露诺从 1 到达 n 最少花费的冰块数。
示例1

输入

复制 
4 6 3 2
1 2 1 3
1 3 3 2
2 4 2 2
3 4 1 3
2 3 1 10
3 2 3 5

输出

复制 
7
示例2

输入

复制 
10 1 1 1
1 2 1 14

输出

复制 
-1

备注:

【样例解释】

对于第一个样例，最佳路径为 1 \to 2 \to 4 ，颜色变化为 1 \to 2 ，费用为 3 + 2 \times 2 = 7 。

对于第二个样例，由于没有从 1 到达 v 的路径，因而无解。

【评测用例规模与约定】

对于 20\% 的数据有：l = 1 。

对于 20\% 的数据有：n \le 100 。

对于 100\% 的测试点，保证 1 \le n \le 5 \times 10^3, 1 \le m \le 3 \times 10^5, 1 \le l \le 64, 2 \le base \le 4 。

对于 100\% 的测试点，保证 1 \le u, v \le n ，1 \le col \le l, 1 \le w \le 10^8 ，保证没有自环。