#include<bits/stdc++.h>
using namespace std;

const int MaxN=1e5+3;

int n,m,s;
long long mi=0x7fffffff;
long long sum;
vector<int> to[MaxN];
vector<int> cost[MaxN];
bool inque[MaxN];
long long dist[MaxN];
int cnt[MaxN];

void add(int u,int v,int w){
	to[u].push_back(v);
	cost[u].push_back(w);
}

bool spfa(){
	for(int i=1;i<=n;i++)dist[i]=0x7fffffff;
	queue<int> que;
	que.push(s);
	dist[s]=0;
	inque[s]=1;

	while(!que.empty()){
		int u=que.front();
		que.pop();
		inque[u]=0;
		if(cnt[u]>n){
			return false;
		}

		for(int i=0;i<to[u].size();i++){
			int v=to[u][i],w=cost[u][i];
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				cnt[v]++;
				if (inque[v])
					continue;
				que.push(v);
				inque[v] = 1;
			}
		}
	}
	return true;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,x;
		cin>>x>>u>>v;
		switch(x){
			case 1:{
				add(u,v,0);
				add(v,u,0);
				break;
			}
			case 2:{
				add(v,u,-1);
				break;
			}
			case 3:{
				add(u,v,0);
				break;
			}
			case 4:{
				add(u,v,-1);
				break;
			}
			case 5:{
				add(v,u,0);
				break;
			}
			if(x%2==0&&u==v){
				cout<<-1;
				return 0;
			}
		}
	}

	for(int i=n;i>=1;i--){
		add(s,i,0);
	}

	if(spfa()){
		for (int i=1;i<=n;i++)
		{
			mi=min(mi,dist[i]);
			sum+=dist[i];
		}
		cout<<sum-n*mi+n;
	}
	else cout<<-1;
	

	return 0;
}