[ZJOI2006]物流运输

物流公司需要将一批货物从码头 $A$ 运往码头 $B$ 。由于货物量较大，运输过程需要持续 $n$ 天，途中通常还需要经过多个码头。

为了便于对运输过程进行严格的管理和跟踪，物流公司通常会预先设计一条固定的运输路线。然而，由于各种因素，某些码头可能会在特定时间段内无法装卸货物，此时必须修改运输路线，以保证货物能够按时到达目的地。

每次修改运输路线都会产生额外成本。请制定一个持续 $n$ 天的运输计划，使运输费用与修改路线所产生的费用之和最小。

输入格式

第一行包含四个整数 $n$ 、 $m$ 、 $K$ 和 $e$ ，分别表示运输所需天数、码头总数、每次修改运输路线的成本以及航线数量。

接下来 $e$ 行，每行包含三个整数，依次表示一条航线连接的两个码头编号以及航线长度。所有航线均为双向航线，单位长度的运输费用为 $1$ 。

码头 $A$ 的编号为 $1$ ，码头 $B$ 的编号为 $m$ 。

接下来一行包含一个整数 $d$ ，表示码头无法使用的时间段数量。

随后 $d$ 行，每行包含三个整数 $P$ 、 $a$ 和 $b$ ，表示编号为 $P$ 的码头在第 $a$ 天至第 $b$ 天期间无法装卸货物，包括第 $a$ 天和第 $b$ 天。同一个码头可能在多个时间段内不可用。

保证任意时刻都至少存在一条从码头 $A$ 到码头 $B$ 的运输路线。

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

总成本为 $n$ 天所采用的运输路线长度之和，加上 $K$ 乘以运输路线的修改次数。

本题为 ZJOI 2006 试题「物流运输」，题面与测试数据整理自 BZOJ。