题目描述

有 $M$ 个集散点和 $E$ 条双向道路，第 $i$ 条道路连接 $U_i$ 和 $V_i$，长度为 $L_i$。每天都需要选择一条从结点 $1$ 到结点 $M$ 的路线，路线费用为所经过道路的长度之和。运输任务持续 $N$ 天。

部分集散点在指定日期内不可使用，路线不能经过当天不可使用的结点。如果连续两天选择的路线不同，还需要支付 $P$ 元换路费用。第一天选择路线不收取换路费用。

请计算 $N$ 天运输的最小总费用。

输入格式

第一行包含四个整数 $N,M,P,E$，分别表示天数、集散点数、换路费用和道路数。

接下来 $E$ 行，每行包含三个整数 $U_i,V_i,L_i$，表示一条双向道路。

下一行包含一个整数 $C$，表示不可用记录数。

接下来 $C$ 行，每行包含三个整数 $X_i,A_i,B_i$，表示集散点 $X_i$ 在第 $A_i$ 天至第 $B_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 2
3 3 3
3 4 4
4 5 5

32

数据范围与提示

• $1\le N\le100$
• $2\le M\le20$
• $1\le P\le500$
• $1\le E\le200$
• $1\le U_i,V_i\le M$
• $1\le L_i\le100$
• $0\le C\le50$
• $1\le X_i\le M$
• $1\le A_i\le B_i\le N$
• 保证每天至少存在一条从结点 $1$ 到结点 $M$ 的可行路线