题目：

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,qq,k,num,u,v,w,head[510],to[6337510],nxt[6337510],val[6337510],dis[6337510],vis[6337510];
struct node{
	int num,dis;
};
void add(int a,int b,int v){
	++num;
	to[num]=b;
	nxt[num]=head[a];
	val[num]=v;
	head[a]=num;
}
bool operator <(node a,node b){
	return a.dis>b.dis;
}
priority_queue<node>q;
void dij(){
	node tt;
	for(int i=1;i<=n;i++){
		dis[i]=INT_MAX;
	}
	tt.dis=dis[1]=0;
	tt.num=1;
	q.push(tt);
	while(!q.empty()){
		int a=q.top().num;
		q.pop();
		if(vis[a]){
			continue;
		}
		vis[a]=1;
		for(int i=head[a];i;i=nxt[i]){
			if(!vis[to[i]]&&dis[a]+val[i]<dis[to[i]]){
				dis[to[i]]=dis[a]+val[i];
				tt.num=to[i];
				tt.dis=dis[to[i]];
				q.push(tt);
			}
		}
	}
}
int main(){
	scanf("%d%d%d%d",&n,&m,&qq,&k);
	int ma=min(n,k);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		for(int i=0;i<ma;i++){
			add(u+i*n,v+i*n,w);
		}
	}
	for(int i=1;i<=qq;i++){
		scanf("%d%d%d",&u,&v,&w);
		for(int i=0;i<ma;i++){
			add(u+i*n,v+i*n,w);
		}
	}
	dij();
	int ans=INT_MAX;
	for(int i=1;i<=ma;i++){
		if(dis[i*n]<ans){
			ans=dis[i*n];
		}
	}
	if(ans==INT_MAX){
		printf("-1");
		return 0;
	}
	printf("%d",ans);
	return 0;
}