rt：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
int n, m, E, head[N], vis[N], tot[N]; ll dis[N];
struct node { int to, nxt, v; } e[300010];
void add(int x, int y, int v) { e[++E] = {y, head[x], v}, head[x] = E; }
int spfa()
{
    memset(tot, 0, sizeof(tot)), memset(vis, 0, sizeof(vis));
    queue<int> q; q.push(0), dis[0] = 0;
    while (!q.empty())
	{
        int x = q.front(); q.pop(); vis[x] = 0;
        for (int i = head[x]; i; i = e[i].nxt)
		{
            int y = e[i].to;
            if (dis[y] < dis[x] + e[i].v) 
			{
                dis[y] = dis[x] + e[i].v, tot[y]++;
                if (tot[y] == n) return 0;
                if (!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return 1;
}

int main()
{
	scanf("%d%d", &n, &m); int flag = 1;
	for (int i = 1, op, x, y; i <= m && flag; i++)
	{
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) add(x, y, 0), add(y, x, 0);
		else if (op == 2) { add(x, y, 1); if (x == y) flag = 0; }
		else if (op == 3) add(y, x, 0);
		else if (op == 4) { add(y, x, 1); if (x == y) flag = 0; }
		else add(x, y, 0);
	} if (!flag) return puts("-1"), 0;
	for (int i = n; i >= 1; i--) add(0, i, 1);
	if (spfa())
	{
		ll ret = 0;
		for (int i = 1; i <= n; i++) ret += dis[i];
		printf("%lld\n", ret);
	} else puts("-1");
	return 0;
}