原理：$spfa$ + SLF + 入队容错 + 队头队尾随机化交换。

有没有人能够优化下。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e6+5;
namespace fio
{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
	//fread->read
	bool IOerror=0;
	inline char nc(){
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if (p1==pend){
			p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if (pend==p1){IOerror=1;return -1;}
			//{printf("IO error!\n");system("pause");for (;;);exit(0);}
		}
		return *p1++;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	inline void read(int &x){bool sign=0; char ch=nc(); x=0;
		for (;blank(ch);ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (;ch>='0'&&ch<='9';ch=nc())x=(x<<3)+(x<<1)+(ch^48);
		if (sign)x=-x;
	}
	inline void read(ll &x){
		bool sign=0; char ch=nc(); x=0;
		for (;blank(ch);ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if (sign)x=-x;
	}
	inline void read(double &x){
		bool sign=0; char ch=nc(); x=0;
		for (;blank(ch);ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if (ch=='.'){
			double tmp=1; ch=nc();
			for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
		}
		if (sign)x=-x;
	}
	inline void read(char *s){
		char ch=nc();
		for (;blank(ch);ch=nc());
		if (IOerror)return;
		for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
		*s=0;
	}
	inline void read(char &c){
		for (c=nc();blank(c);c=nc());
		if (IOerror){c=-1;return;}
	}
	//fwrite->write
	struct Ostream_fwrite{
		char *buf,*p1,*pend;
		Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
		void out(char ch){
			if (p1==pend){
				fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
			}
			*p1++=ch;
		}
		void print(int x){
			static char s[15],*s1;s1=s;
			if (!x)*s1++='0';if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
		}
		void println(int x){
			static char s[15],*s1;s1=s;
			if (!x)*s1++='0';if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1); out('\n');
		}
		void print(ll x){
			static char s[25],*s1;s1=s;
			if (!x)*s1++='0';if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
		}
		void println(ll x){
			static char s[25],*s1;s1=s;
			if (!x)*s1++='0';if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1); out('\n');
		}
		void print(double x,int y){
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
				1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
				100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
			if (x<-1e-12)out('-'),x=-x;x*=mul[y];
			ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
			ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
			if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
		}
		void println(double x,int y){print(x,y);out('\n');}
		void print(char *s){while (*s)out(*s++);}
		void println(char *s){while (*s)out(*s++);out('\n');}
		void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
		~Ostream_fwrite(){flush();}
	}Ostream;
	inline void print(int x){Ostream.print(x);}
	inline void println(int x){Ostream.println(x);}
	inline void print(char x){Ostream.out(x);}
	inline void println(char x){Ostream.out(x);Ostream.out('\n');}
	inline void print(ll x){Ostream.print(x);}
	inline void println(ll x){Ostream.println(x);}
	inline void print(double x,int y){Ostream.print(x,y);} //y为小数点后几位
	inline void println(double x,int y){Ostream.println(x,y);}
	inline void print(char *s){Ostream.print(s);}
	inline void println(char *s){Ostream.println(s);}
	inline void println(){Ostream.out('\n');}
	inline void flush(){Ostream.flush();} //清空
#undef OUT_SIZE
#undef BUF_SIZE
}
struct Edge
{
	int to, next, val;
	Edge()
	{	}
	Edge(int to_, int next_, int val_)
	{
		to=to_;
		next=next_;
		val=val_;
	}
} edge[MAX];
int head[MAX], vis[MAX], cont[MAX], cnt;
long long dis[MAX];
void add(int u, int v, int w)
{
	edge[++cnt] = Edge(v, head[u], w);
	head[u] = cnt;
}
bool spfa(int n)
{
	for (register int i = 0; i < n; i++)
	{
		dis[i] = -100000000;
	}
	memset(vis, 0, sizeof(vis));
	memset(cont, 0, sizeof(cont));
	deque<int> q;
	q.push_back(n);
	dis[n] = 0;
	while (!q.empty())
	{
		int u = q.front();
		q.pop_front();
		vis[u] = 0;
		for (register int i = head[u]; i != 0; i = edge[i].next)
		{
			register int v = edge[i].to, w = edge[i].val;
			if (dis[v] < dis[u] + w)
			{
				dis[v] = dis[u] + w;
				//cout << dis[v]<<" ";
				if (!vis[v])
				{
					if(!q.empty()&&dis[v]<dis[q.front()]+15)
					{
						q.push_front(v);
					}
					else
					{
						q.push_back(v);
					}
					if(q.size()>1&&dis[q.front()]>dis[q.back()])
					{
						swap(q.front(),q.back());
					}
					if(rand()%4)
					{
						swap(q.front(),q.back());
					}
					vis[v] = 1;
					cont[v]++;
					if (cont[v] >= n)
						return false;
				}
			}
		}
	}
	return true;
}

int main() {
	int n, k;
	fio::read(n);
	fio::read(k);
	for (register int i = 0; i < k; i++)
	{
		int x,u,v;
		fio::read(x);fio::read(u);fio::read(v);
		switch (x)
		{
		case 1:
			add(u, v, 0);
			add(v, u, 0);
			break;
		case 2:
			if (u == v)
			{
				fio::println(-1);
				return 0;
			}
			add(u, v, 1);
			break;
		case 3:
			add(v, u, 0);
			break;
		case 4:
			if (u == v)
			{
				fio::println(-1);
				return 0;
			}
			add(v, u, 1);
			break;
		case 5:
			add(u, v, 0);
		}
	}
	for (register int i = n; i >= 1; i--)
	{
		add(n + 1, i, 1);
	}
	bool t = spfa(n + 1);
	if (t)
	{
		long long ans = 0;
		for (register int i = 1; i <= n; i++) {
			// cout << dis[i] << " ";
			ans += dis[i];
		}
		fio::println(ans);
	} 
	else 
	{
		fio::println(-1);
	}
	return 0;
}