代码如下，广搜+dp：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 500;
int head[maxn], cnt, vis[maxn], ds[maxn][maxn], n, m, k, ee, p, x, y, z, co[maxn][maxn];
struct E {
	int v, w, last;
}e[maxn<<4];

void add(int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].last = head[u];
	head[u] = cnt;
}

int t;
struct node {
	int u, w;
};

int cl, op;
int dp[maxn];

int bfs() {
	node Q[maxn<<6];
	cl = op = 1; int ans = 100000000;
	Q[1].u = 1; Q[1].w = 0;
	for(;cl <= op; cl++) {
		if(Q[cl].u == m) {
			ans = min(ans, Q[cl].w);
			continue;
		}
		int u = Q[cl].u;
		for(int i = head[u]; i; i = e[i].last) {
			if(!vis[e[i].v]) {
				Q[++op].u = e[i].v;
				Q[op].w = Q[cl].w+e[i].w;
			}
		}
		vis[u] = 1;
	}
	return ans;
}

int xx;
signed main() {
	cin >> n >> m >> k >> ee;
	for(int i = 1; i <= ee; i++) {
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z);
	}
	cin >> xx;
	while(xx--) {
		cin >> z >> x >> y;
		for(int i = x; i <= y; i++) 
		  ds[z][i] = 1;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			memset(vis, 0, sizeof(vis));
			for(int l = 1; l <= m; l++) {
				for(int r = i; r <= j; r++)
				  if(ds[l][r]) vis[l] = 1;
			}
			co[i][j] = bfs();
		}
	}
	memset(dp,0x7f,sizeof(dp));
	for(int i = 1; i <= n; i++) {
		dp[i] = co[1][i]*i;
		for(int j = i-1; j >= 0; j--) {
			dp[i] = min(dp[i], dp[j] + co[j+1][i]*(i-j) + k);
		}
	}
	cout << dp[n];
	return 0;
}