题目描述 Description
PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。
PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他秒要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。
因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。
N<=300，M<=5000 ，T<=50；
输入描述 Input Description
第一行有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这几天都会受灾害。
输出描述 Output Description
T天在道路的防守上花费最少的军粮。
样例输入 Sample Input
3 3 5 10 30
1 2 1
2 3 2
1 3 4
1
1 3 2 5
样例输出 Sample Output
180
数据范围及提示 Data Size & Hint
各个测试点1s
/*
这道题和物流运输这道题非常像，还是枚举i~j天的最小生成树，然后 搞一搞区间dp，一开始并查集都打错了- -!智障
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define fd(i,l,r) for(int i = r;i >= l;i--)
using namespace std;
const int N = ,M=;
ll read(){
ll x=,f=;
char ch=getchar();
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
struct edge{
int u;
int v;
ll w;
friend bool operator < (edge a,edge b){
return a.w < b.w;
}
}e[M];
ll n,m,t,k,val,p,sumv;
ll rec[][],dp[];
bool zh[][][],vis[M];
int cnt,fa[N],tot;
int findf(int x){
return x == fa[x] ? fa[x] : fa[x] = findf(fa[x]);
}
void input(){
n=read();m=read();t=read();val=read();k=read();
fo(i,,m){
e[i].u = read();
e[i].v = read();
if(e[i].u > e[i].v) swap(e[i].u,e[i].v);
e[i].w = read();
sumv += e[i].w;
}
p =read();
int u,v,t1,t2;
fo(i,,p){
u = read();v = read();t1 = read();t2 = read();
if(u > v) swap(u,v);
if(t1 > t2) swap(t1,t2);
fo(j,t1,t2) zh[u][v][j] = true;
}
}
void mst(int lp,int rp){
int u,v;
int cnt_n = ;
fo(i,,m){
fo(j,lp,rp){
if(zh[e[i].u][e[i].v][j]){
vis[i] = true;
break;
}
}
}
fo(i,,m){
u = findf(e[i].u);
v = findf(e[i].v);
if(fa[u] == v || vis[i]) continue;
fa[u] = v;
tot += e[i].w * val;
cnt_n++;
if(cnt_n == n-) break;
}
if(cnt_n != n-) rec[lp][rp] = 987654321012345LL;
else rec[lp][rp] = tot*(rp-lp+);
}
void get_rec(){
sort(e+,e++m);
fo(i,,t){
fo(k,i,t){
fo(j,,N) fa[j] = j;
fo(j,,m) vis[j] = false;
tot = ;
mst(i,k);
}
}
}
void get_ans(){
fo(i,,) dp[i] = 987654321012345LL;
fo(i,,t){
fd(j,,i){
dp[i] = min(dp[i],rec[j][i] + dp[j-] + k);
}
}
cout<<dp[t]<<endl;
}
int main(){
input();
get_rec();
get_ans();
return ;
}