一支参赛队将在 K 国参加连续 N 天的比赛。城市中共有 M 个地点，编号为 1\sim M；队伍每天都要从驻地 1 前往赛场 M。地点之间有 E 条双向道路，第 i 条道路连接 u_i,v_i，通行代价为 w_i。
每天出发前，队伍需要选定一条从 1 到 M 的简单路径作为完整通勤路线，并支付该路线的道路代价之和。部分中转地点会在指定日期暂停开放；当天选择的路线不能经过任何暂停开放的地点。
两条通勤路线被认为相同，当且仅当它们经过的地点序列完全相同。为了减少临时调整，若第 d 天与第 d-1 天选择的完整路线不同，则还要支付一次固定调整代价 P。第一天选择路线不需要支付调整代价。因此总成本为
\text{每天的路线代价之和}+P\times\text{相邻两天路线发生改变的次数}.
请计算完成全部 N 天通勤的最小总成本。
第一行输入四个整数 N,M,P,E。
接下来 E 行，每行输入三个整数 u,v,w，表示一条代价为 w 的双向道路。
接下来一行输入整数 C，表示暂停开放记录数。
接下来 C 行，每行输入三个整数 x,l,r，表示地点 x 在第 l 天至第 r 天（含两端）暂停开放。同一地点可以出现在多条记录中。
输出一个整数，表示最小总成本。
4 4 6 5 1 2 2 2 4 2 1 3 3 3 4 2 1 4 10 2 3 1 1 2 3 4
24
6 5 0 7 1 2 2 2 5 3 1 3 4 3 5 2 1 4 6 4 5 1 1 5 12 3 2 2 3 3 4 5 4 6 6
32
10 6 15 10 1 2 3 2 6 4 1 3 5 3 6 3 1 4 6 4 5 1 5 6 2 2 3 2 3 4 2 1 6 20 5 2 4 6 3 1 2 4 7 9 5 8 10 2 10 10
92
第 1,2 天使用路线 1\to2\to4，每天代价为 4；第 3,4 天使用路线 1\to3\to4，每天代价为 5。路线改变一次，总代价为 2\times4+6+2\times5=24。
若四天始终使用直达道路，总代价为 40；频繁逐日改变路线也不会更优。
本组数据满足 P=0，每天可以独立选择当日最短路线。六天的最短路线代价依次为 5,6,6,5,5,5，总成本为 5+6+6+5+5+5=32。这展示了特殊性质 A。
对于所有测试数据，保证：
本题共 10 个测试点，每个测试点 10 分。
| 测试点 | N\le | M\le | 特殊性质 |
|---|---|---|---|
| 1 | 1 | 5 | 无 |
| 2 | 6 | 8 | 无 |
| 3 | 10 | 10 | 无 |
| 4 | 100 | 20 | A |
| 5 | 100 | 20 | B |
| 6 | 30 | 12 | 无 |
| 7 | 50 | 15 | 无 |
| 8\sim10 | 100 | 20 | 无 |
特殊性质 A： P = 0。
特殊性质 B： C = 0，即所有地点在全部日期均开放。