#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int n, k, dis[100005], vis[100005], sum[100005];
vector<int> g[100005], w[100005];
queue<int> q;

void add(int x, int y, int z)
{
	g[x].push_back(y);
	w[x].push_back(z);
}

bool spfa(int s)
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push(s);
	vis[s] = true;
	
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[x] = false;
		for(int i = 0; i < g[x].size(); i++)
		{
			int y = g[x][i];
			if(dis[y] > dis[x] + w[x][i])
			{
				dis[y] = dis[x] + w[x][i];
				if(vis[y] == false)
				{
					q.push(y);
					vis[y] = true;
					sum[y]++;
					if(sum[y] >= n) return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	cin >> n >> k;
	for(int i = 1; i <= k; i++)
	{
		int x, u, v;
		cin >> x >> u >> v;
		switch(x)
		{
			case 1: add(v, u, 0); add(u, v, 0); break;
			case 2: add(u, v, -1); break;
			case 3: add(v, u, 0); break;
			case 4: add(v, u, -1); break;
			case 5: add(u, v, 0); break;
		}
	}
	
	for(int i = 1; i <= n; i++)
		add(0, i, -1); //ti - 0 >= 1
	
	if(spfa(0) == true) cout << -1 << endl;
	else
	{
		long long ans = 0;
		for(int i = 1; i <= n; i++)
			ans += dis[i];
		cout << -ans << endl;
	}
	
	return 0;
}