题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。当地部门正在对村庄进行重建。

B 地区共有 $N$ 个村庄，编号从 $1$ 到 $N$。有 $M$ 条双向通行的公路。

现在村庄 $1$ 和村庄 $N$ 已经重建完成。

题目描述

有一批物资要从村庄 $1$ 运送到村庄 $N$。由于物资较多，但只有一辆卡车，所以计划分成 $D$ 天运输，每天运送一次。

但是有些村庄还在重建中。已知村庄 $i$ 施工的时间为第 $s_i$ 天到第 $e_i$天，在这个时间段内是不允许通行的。同一个村庄可能有多个时间段施工。即使没有重建完成，只要不在施工期，该村庄也是可以通行的。

在每一天内，卡车要按设计路线运输物资。卡车不能途经当天正在施工的村庄。运输过程中，经过每条公路都需要缴纳相应的过路费。每天都至少存在一条从村庄 $1$ 到村庄 $N$ 的路线。在第一天，设计运输路线是不需要支付费用的。如果之后某一天要更改成与前一天不同的线路，则要付出 $C$ 的费用。卡车每天运输完成返回村庄 1 的路途中不再缴纳过路费。

问：完成运输的最少总费用是多少？（只考虑过路费和更改路线费用）

输入格式

第一行：四个整数 $D,N,C,M$。

接下来 $M$ 行：每行三个整数 $u, v, w$，表示村庄 $u$ 和 $v$ 之间有一条双向公路，经过这条公路需要支付 $w$ 的过路费。

接下来一行：一个整数 $K$，表示有 $K$ 条重建信息。

接下来$K$ 行：每行三个整数 $i,s_i,e_i$。表示村庄 $i$ 在 $[s_i, e_i]$ 天之内施工。同一个村庄可能有多个时间段施工，每个时间段都不相交。

输出格式

一个整数，表示最少总费用。

样例输入

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

样例输出

32

样例解释

前 3 天的路线：$1 → 4 → 5$，后 2 天走 $1 → 3 → 5$，这样总费用为 $(2+2)\times 3+(3+2)\times 2+10=32$。

数据范围

对于 $100\%$ 的数据，$1 \le D \le 100$，$1\le N \le 20$, $1 \le C \le 500$, $1 \le M \le 200$, $1 \le K \le 50$, $s_i \le e_i$。