题目描述

物流公司要把一批货物从码头 $\red A$ 运到码头 $\red B$

由于货物量比较大，需要 $\red n$ 天才能运完

货物运输过程中一般要转停好几个码头

物流公司通常会设计一条固定的运输路线，以便对 整个运输过程实施严格的管理和跟踪

由于各种因素的存在，有的时候某个码头会无法装卸 货物，这时候就必须修改运输路线，让货物能够按时到达目的地

但是修线是一件十分麻烦 的事情，会带来额外的成本

因此物流公司希望订一个 $\red n$ 天的运输计划，使得总成本尽可能 地小

输入格式

第一行是四个整数 $\red {n(1≤n≤100)}$、$\red {m(1≤m≤20)}$、$\red K$ 和 $\red e$

$\red n$ 表示物运输货物所需天数， $\red m$ 表示码头总数，$\red K$ 表示每次修改运输路线路所需成本

接下来 $\red e$ 行，每行是一条航线描述， 包括了三个整数，依次表示航线连接的两个码头编号以及航线长度($\red {>0}$)

其中码头 $\red A$ 编号为 $\red 1$，码头 $\red B$ 编号为 $\red m$

单位长度的运输费用为 $\red 1$，航线是双向的

再接下来一行是一个整数 $\red d$,后面的 $\red d$ 行每行是三个整数 $\red {P(1<=P<=m)}$,$\red a$,$\red {b(1<=a<=b<=n)}$

表示编号为 $\red P$ 的码头从第 $\red a$ 天到第 $\red b$ 天无法装卸货物(含头尾)

同一个码头有可能在多个时间段内不可用

但任何时 间都存在至少一条从码头 $\red A$ 到码头 $\red B$ 的运输路线

输出格式

包括了一个整数表示最小的总成本

总成本$\red {=n}$ 天运输路线长度之和+k*改变运输路线的 次数

样例

输入样例

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

提示

样例说明

上图依次表示第 $\red 1$ 天至第 $\red 5$ 天的情况，阴影表示不可以用的码头

前三天走 $\red {1-4-5}$，后两天走 $\red {1-3-5}$，这样总成本为$\red {(2+2)*3+(3+2)*2+10=32}$