题目背景

$update$ $on$ $2023.8.17$ $12:25$ 数据修复&加强完成，可重新提交代码。

路虽远，行则将至。

题目描述

请注意本题特殊的时限。

小 X 来到了 Z 市，Z 市有 $n$ 个交通路口，$m$ 条马路。其中第 $i$ 条马路连接着第 $u_i$ 个交通路口和第 $v_i$ 个交通路口（可以从 $u_i$ 到 $v_i$，也可以从 $v_i$ 到 $u_i$），小 X 通过这条马路时要花费 $p_i$ 秒，若有限速，则通过这条马路时要花费 $q_i$ 秒。

现在，市长要在 $k$ 条马路上添加限速，然而，要在哪 $k$ 条马路上限速是小 X 自己规定的。

同时，市长会在每个交通路口处添加红绿灯。第 $i$ 个交通路口的红绿灯先亮绿灯 $x_i$ 秒，再亮黄灯 $y_i$ 秒，之后亮红灯 $z_i$ 秒，然后再亮绿灯，黄灯，红灯，如此往复。如果一个交通路口的红绿灯不是红灯，小 X 可以从这个交通路口出发，到达另一个交通路口。若到达交通路口时，灯的颜色瞬间变了，则按照变了之后的灯计算，灯的黄灯和红灯的持续时间可能为 $0$。并且，小 X 最多只能闯 $g$ 次黄灯。

过了一会儿，市长突然发现，所有的红绿灯在某一刻都变成了绿灯。与此同时，小 X 从第 $1$ 个路口出发，前往第 $n$ 个路口。他想问你，他至少要花多少时间才能到达第 $n$ 个路口？

因为路虽远，行则将至，数据保证一定可以到达，即 $1\sim n$ 一定连通。

输入格式

第 $1$ 行 $4$ 个整数 $n,m,k,g$。

接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,z_i$。

接下来 $m$ 行，每行 $4$ 个整数 $u_i,v_i,p_i,q_i$。

输出格式

一行，为小 X 花费的最少的时间。

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

4

9 16 14 2
1 7 2
1 5 3
1 6 4
3 5 0
1 6 5
1 0 4
1 7 5
3 8 8
3 8 6
1 2 1 4
8 5 2 6
2 4 2 4
8 6 3 5
3 4 0 2
6 7 1 4
1 5 7 8
5 9 16 21
1 3 2 2
7 6 2 3
5 4 2 3
6 9 3 5
2 5 2 4
8 9 4 7
1 4 4 7
6 5 6 9

18

提示

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$，$0 \le k,g \le m$，$1 \le x_i \le 10^9$，$0 \le y_i,z_i \le 10^9$，$1 \le u,v \le n$，$0 \leq p_i \leq q_i \leq 10^9$。

样例解释 #1：

$1 \to 3 \to 4 \to 5$ 并在编号为 $1,2,4,6,7,8$ 的马路上添加限速，到 $3$ 时闯黄灯，到 $4$ 时绿灯直接过，这时候，$1 \to 3$ 花费 $1$ 秒，$3 \to 4$ 花费 $0$ 秒，$4 \to 5$ 花费 $3$ 秒，共花费 $4$ 秒。

样例解释 #2：

$1 \to 2 \to 5 \to 6 \to 9$ 并在编号为 $2,3,4,5,6,7,8,9,10,11,13,14,15,16$ 的马路上添加限速，到 $2,5$ 时闯黄灯，到 $4$ 时绿灯直接过，到 $6$ 时等 $1$ 秒红灯，这时候，$1 \to 2$ 花费 $1$ 秒，$2 \to 5$ 花费 $4$ 秒，$5 \to 6$ 花费 $9$ 秒，$6 \to 9$ 花费 $3$ 秒，加上等红灯的 $1$ 秒共花费 $18$ 秒。