SPFA 已过

#include <bits/stdc++.h>
using namespace std;
#define N 300010
int u[N],v[N],w[N],dis[N],vis[N],cnt[N];
vector <int> vc[N];
bool cmp(int a,int b){
	return w[a]>w[b];
}int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	int n,m,tot=0,mn=0,C=0; cin>>n>>m;
	long long sum=0;
	for (int i=1; i<=m; i++){
		int x,a,b; cin>>x>>a>>b;
		if (x==1){
			tot++; u[tot]=b; v[tot]=a; 
			tot++; u[tot]=a; v[tot]=b;
		}else if (x==2){
			tot++; u[tot]=b; v[tot]=a; w[tot]=1;
		}else if (x==3){
			tot++; u[tot]=a; v[tot]=b;
		}else if (x==4){
			tot++; u[tot]=a; v[tot]=b; w[tot]=1;
		}else{
			tot++; u[tot]=b; v[tot]=a;
		}
	}for (int i=1; i<=n; i++){
		tot++; u[tot]=n+1; v[tot]=i; w[tot]=0;
	}for (int i=1; i<=tot; i++){
		if (u[i]<=n) swap(u[i],v[i]);
		vc[u[i]].push_back(i);
	}for (int i=1; i<=n; i++){
		sort(vc[i].begin(),vc[i].end(),cmp);
	}queue <int> q; q.push(n+1); vis[n+1]=1;
	memset(dis,-0x3f,sizeof(dis)); dis[n+1]=0;
	while (!q.empty()){
		int u=q.front(); q.pop(); vis[u]=0; //cout<<u<<"\n";
		for (auto x:vc[u]){
			//cout<<dis[v[x]]<<" "<<dis[u]<<" "<<w[x]<<"\n";
			if (dis[v[x]]<dis[u]+w[x]){
				dis[v[x]]=dis[u]+w[x];
				if (!vis[v[x]]){
					vis[v[x]]=1; q.push(v[x]); cnt[v[x]]++;
					if (cnt[v[x]]>n){
						cout<<"-1"; return 0;
					}C++;
					if (C>2e7){
						cout<<"-1"; return 0;
					} 
				}
			}
		}
	}for (int i=1; i<=n; i++){
		mn=min(mn,dis[i]);
		//cout<<dis[i]<<"\n";
	}for (int i=1; i<=n; i++){
		sum+=dis[i]-mn;
	}cout<<sum+n;
	return 0;
}