30pts，正确了#1,#2,#3

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
#define se second
#define fi first
using namespace std;
const ll N=509;
ll n,m,k,e,spd[N][N],dp[N],vis[N],d,dis[N],put[N];
P stop[N];
vector<P>edge[N];
inline void dijstra()
{
	for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	queue<ll>que;dis[1]=0;put[1]=1;
	que.push(1);memset(put,0,sizeof(put));
	while(!que.empty())
	{
		ll x=que.front();
		que.pop();
		put[x]=0;
		for(auto i:edge[x])
			if(vis[i.fi] && dis[i.fi]>dis[x]+i.se)
			{
				dis[i.fi]=dis[x]+i.se;
				if(!put[i.fi])
					que.push(i.fi),
					put[i.fi]=1;
			}
	}
}
int main()
{
	cin>>e>>n>>k>>m;
	for(int i=1,x,y,z;i<=m;i++)
		cin>>x>>y>>z,
		edge[x].pb(mp(y,z)),
		edge[y].pb(mp(x,z));
	cin>>d;
	for(int i=1,x,y,z;i<=d;i++)
		cin>>x>>y>>z,
		stop[x].fi=y,
		stop[x].se=z;
	for(int i=1;i<=e;i++)
		for(int j=i;j<=e;j++)
		{
			memset(vis,0,sizeof(vis));
			for(int k=1;k<=n;k++)
				if(stop[k].se<i || stop[k].fi>j)
					vis[k]=1;
			dijstra();
			spd[i][j]=dis[n];
		}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=e;i++)
	{
		dp[i]=min(dp[i],spd[1][i]*i);
		for(int j=i-1;j>=1;j--)
			if(spd[j+1][i]!=INT_MAX)
				dp[i]=min(dp[i],dp[j]+spd[j+1][i]*(i-j)+k);
	}
	cout<<dp[e];
	return 0;
}