WA on #9

#include<bits/stdc++.h>
using namespace std;
int mv,n,m,s,st;
vector<pair<int,int>> edge[505];
int f[505];
int ind[505];
int cnt[505];
int dist[505];
bool vis[505];

int spfa() {
	memset(dist,0x3f3f3f3f,sizeof(dist));
	queue<int> q;
	vis[st]=1;
	dist[st]=0;
	q.push(st);
	while(!q.empty()) {
		int index=q.front();
		q.pop();
		vis[index]=0;
		cnt[index]++;
		if(cnt[index]>=n) {
			cout<<-1;
			return 0;
		}
		for(auto to:edge[index]) {
			int x=to.first;
			int y=to.second;
			if(dist[x]>dist[index]+y) {
				dist[x]=dist[index]+y;
				if(!vis[x]) {
					vis[x]=1;
					q.push(x);

				}
			}
		}
	}
	return 0;
}
signed main() {
	cin>>mv>>m>>n>>s;
	for(int i=1; i<=m; i++) {
		int in,to;
		cin>>in>>to;
		edge[in].push_back(make_pair(to,-mv));
	}
	for(int i=1; i<=s; i++) {
		int in,to,w;
		cin>>in>>to>>w;
		edge[in].push_back(make_pair(to,w-mv));
	}
	st=n+1;
	for(int i=1; i<=n; i++) {
		edge[st].push_back(make_pair(i,-mv));
	}
	spfa();
	int ans=0x3f;
	for(int i=1; i<=n; i++) {
		ans=min(ans,dist[i]);
	}
	cout<<-ans<<endl;
	return 0;
}