当前没有测试数据。

题目描述

一家农业合作社需要将新鲜农产品从种植基地 $S$ 运送到加工厂 $T$。由于农产品产量巨大，运输任务需要连续 $N$ 天完成。在运输过程中，农产品需要通过若干集散点进行中转。

为方便管理，合作社通常会规划一条固定的运输路线。然而，由于季节性天气或道路维护等原因，某些集散点在特定日期可能无法正常使用。此时，合作社需要调整运输路线以确保农产品顺利送达加工厂。

农产品运输，本身存在运输成本。调整运输路线会增加额外的调度成本，因此合作社希望制定一个 $N$ 天的运输计划，使总成本最小。

总成本由：每日运输路线的总距离费用（每单位距离费用为 $1$ 元），加上调整路线的固定调度成本构成。

更加详细的讲，总成本 $=$ $N$ 天运输路线距离之和 $+$ $P×$ 调整运输路线的次数。（$P$ 为每次调整运输路线的固定的调度成本）

你的任务是帮助合作社计算最优的 $N$ 天运输计划，求出最小的总成本。

输入格式

第一行读入四个整数 $N, M, P, E$，含义如下。

• $N$ 表示运输任务所需的天数。
• $M$ 表示集散点总数（种植基地 $S$ 编号为 $1$，加工厂 $T$ 编号为 $M$）。
• $P$ 表示每次调整运输路线所需的固定调度成本。
• $E$ 表示可用的运输路线数量。

接下来 $E$ 行，每行包含三个整数 $U_i, V_i, L_i$，表示一条连接集散点 $U_i$ 和 $V_i$ 的双向运输路线，路线距离为 $L_i$。

接下来一行包含一个整数 $C$，表示集散点不可用的记录数。随后 $C$ 行，每行包含三个整数 $X_i, A_i, B_i$，表示编号为 $X_i$ 的集散点在第 $A_i$ 天到第 $B_i$ 天（包含 $A_i$ 和 $B_i$）无法使用。同一个集散点可能在多个时间段不可用，但任何时候都存在至少一条从 $S$ 到 $T$ 的运输路线。

输出格式

输出一个整数，表示最小的总成本。

样例 #1

输入

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 2
3 3 3
3 4 4
4 5 5

输出

32

数据范围

对于所有的测评数据，满足：

• $1 \le N \le 100$，$1 \le M \le 20$，$1 \le P \le 500$，$1 \le E \le 200$。
• $1 \le U_i, V_i \le M$，$1 \le L_i \le 100$。
• $1 \le C \le 50$，$1 \le X_i \le M$，$1 \le A_i \le B_i \le N$。