背景故事

初中班上有一个同学叫彭湃，我们取的外号就是 pp。

题目描述

PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路 Wij 受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路 Wij，至少需要 Kij 个士兵才能守住）。
PP 可真是高手，不一会，就攻下了 N - 1 座城市，加上原来的就有 N 座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP 估算了一下，大概需要 T 天。他现在无暇分身进攻了，只好在这 T 天内好好的搞建设了。所以他要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉 V 的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要 K 的军粮，初始方案也需要 K 的军粮）。因为游戏是 PP 编的，所以他知道什么时候有灾害。PP 可是一个很节约的人，他希望这 T 天在道路的防守上花最少的军粮。

输入格式

第一行有 5 个整数 N，M，T，V，K。N 表示有城市数，M 表示道路数，T 表示需要修养的天数，V 表示每个士兵每天吃掉的军粮数，K 表示修改一次花掉的军粮数。
以下 M 行，每行 3 个数 A，B，C。表示 A 与 B 有一条路（路是双向的）需要 C 个士兵才能守住。
第 M + 2 行是一个数 P，表示有P 个灾害。
以下 P 行，每行 4 个数，X，Y，T1，T2。表示 X 到 Y 的这条路，在 T1 到 T2 这几天都会受灾害。

输出格式

T 天在道路的防守上花费最少的军粮。

样例输入

3 3 5 10 30
1 2 1
2 3 2
1 3 4
1
1 3 2 5

样例输出

180

数据范围

对于 100%数据，N <= 300，M <= 5000 ，T <= 50，P <= 8000。

限制

1s

来源

CWOI新高二专题测试⑨