#include<bits/stdc++.h>
using namespace std;
int head[1005],dis[1005];
int tot,d,f,n,m,s;
bool vis[1005];
int cnt[1005];
struct edge{
	int to,nxt,w;
}e[1005];
struct node{
	int id,dist;
	bool operator <(const node &next)const{
		return dist<next.dist;
	}
};
void add(int u,int v,int w){
	tot++;
	e[tot].to=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
	return;
}
void Dijkstra(int s){
	for(int i=1;i<=n;i++){
		dis[i]=-1e9;
	}
	dis[s]=0;
	priority_queue<node>pq;
	node cur={s,0};
	pq.push(cur);
	while(!pq.empty()){
		cur=pq.top();
		pq.pop();
		if(vis[cur.id]){
			continue;
		} 
		vis[cur.id]=1;
		cnt[cur.id]++;
		if(cnt[cur.id]>n){
			puts("-1");exit(0);
		}
		for(int i=head[cur.id];i!=0;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]<dis[cur.id]+e[i].w){
				dis[v]=dis[cur.id]+e[i].w;
				node jd={v,dis[v]};
				pq.push(jd);
			}
		}
	}
}
int main(){
	cin>>d>>m>>n>>f>>s;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v,d);
	}
	for(int i=1;i<=f;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,d-w);
	}
	Dijkstra(s);
	int maxi=-1;
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
		maxi=max(maxi,dis[i]);
	}
	cout<<maxi;
	return 0;
}

题解都是$SPFA$,但是我们刚学$Dijkstra$,又没学$SPFA$,但是有负边权，所以有什么办法吗？？？（求助！！！）