{"raw_statement":[{"iden":"background","content":"$update$ $on$ $2023.8.17$ $12:25$ \n**数据修复&加强完成，可重新提交代码。**\n\n路虽远，行则将至。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ugqt01zi.png)"},{"iden":"statement","content":"**请注意本题特殊的时限。**\n\n小 X 来到了 Z 市，Z 市有 $n$ 个交通路口，$m$ 条马路。其中第 $i$ 条马路连接着第 $u_i$ 个交通路口和第 $v_i$ 个交通路口（可以从 $u_i$ 到 $v_i$，也可以从 $v_i$ 到 $u_i$），小 X 通过这条马路时要花费 $p_i$ 秒，若有限速，则通过这条马路时要花费 $q_i$ 秒。\n\n现在，市长要在 $k$ 条马路上添加限速，然而，要在哪 $k$ 条马路上限速是小 X 自己规定的。\n\n同时，市长会在每个交通路口处添加红绿灯。第 $i$ 个交通路口的红绿灯先亮绿灯 $x_i$ 秒，再亮黄灯 $y_i$ 秒，之后亮红灯 $z_i$ 秒，然后再亮绿灯，黄灯，红灯，如此往复。如果一个交通路口的红绿灯不是红灯，小 X 可以从这个交通路口出发，到达另一个交通路口。若到达交通路口时，灯的颜色瞬间变了，则按照变了之后的灯计算，灯的黄灯和红灯的持续时间可能为 $0$。并且，小 X 最多只能闯 $g$ 次黄灯。\n\n过了一会儿，市长突然发现，所有的红绿灯在某一刻都变成了绿灯。与此同时，小 X 从第 $1$ 个路口出发，前往第 $n$ 个路口。他想问你，他至少要花多少时间才能到达第 $n$ 个路口？\n\n因为路虽远，行则将至，数据保证一定可以到达，即 $1\\sim n$ 一定连通。"},{"iden":"input","content":"第 $1$ 行 $4$ 个整数 $n,m,k,g$。\n\n接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,z_i$。\n\n接下来 $m$ 行，每行 $4$ 个整数 $u_i,v_i,p_i,q_i$。"},{"iden":"output","content":"一行，为小 X 花费的最少的时间。"},{"iden":"note","content":"**本题采用捆绑测试。**\n\n| Subtask | $n,m$ | $y_i,z_i$ | $k,g$ | 分值 |\n| :-: | :-: | :-: | :-: | :-: |\n| $0$ | $1 \\le n,m \\le 5$ | 无特殊限制 | 无特殊限制 | $20$ |\n| $1$ | 无特殊限制 | $y_i=z_i=0$ | $k=g=0$ | $5$ |\n| $2$ | 无特殊限制 | $y_i=0,0 \\le z_i \\le 10^9$ | 无特殊限制 | $25$ | \n| $3$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | $50$ |\n\n对于 $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$。\n### 样例解释 #1：\n\n\n$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$ 秒。\n\n### 样例解释 #2：\n\n$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$ 秒。"}],"translated_statement":null,"sample_group":[["5 8 6 1\n1 2 2\n1 0 3\n1 1 4\n3 1 0\n5 1 4\n1 2 1 4\n2 4 2 4\n3 4 0 2\n1 5 7 8\n1 3 1 2\n5 4 2 3\n2 5 2 4\n1 4 4 7","4"],["9 16 14 2\n1 7 2\n1 5 3\n1 6 4\n3 5 0\n1 6 5\n1 0 4\n1 7 5\n3 8 8\n3 8 6\n1 2 1 4\n8 5 2 6\n2 4 2 4\n8 6 3 5\n3 4 0 2\n6 7 1 4\n1 5 7 8\n5 9 16 21\n1 3 2 2\n7 6 2 3\n5 4 2 3\n6 9 3 5\n2 5 2 4\n8 9 4 7\n1 4 4 7\n6 5 6 9","18"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}