#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

#define maxn 800005

int n,k,flag=0;

int h[maxn],to[maxn],ne[maxn],en=0,w[maxn],inq[maxn],tim[maxn];

queue <int> q;

ll dis[maxn],ans;

void add(int a,int b,int c)

{

    to[en]=b;ne[en]=h[a];w[en]=c;h[a]=en++;

}

void SPFA()

{

    memset(dis,-1,sizeof dis);

    dis[0]=0;inq[0]=1;q.push(0);tim[0]++;

    while (!q.empty())

    {

        int x=q.front(); q.pop(); inq[x]=0;

        for (int i=h[x];i>=0;i=ne[i])

        if (dis[to[i]]<dis[x]+w[i]){

            dis[to[i]]=dis[x]+w[i];

            if (!inq[to[i]])

            {

                inq[to[i]]=1;

                tim[to[i]]++;

                if (tim[to[i]]>n)

                {

                    printf("-1\n");

                    return ;

                }

                q.push(to[i]);

            }

        }

    }

    F(i,1,n) ans+=dis[i];

    printf("%lld\n",ans);

}

int main()

{

    memset(h,-1,sizeof h);

    scanf("%d%d",&n,&k);

    F(i,1,k)

    {

        int x,a,b;scanf("%d%d%d",&x,&a,&b);

        switch(x)

        {

            case 1: add(a,b,0);add(b,a,0);break;

            case 2: add(a,b,1); if (a==b) flag=1; break;

            case 3: add(b,a,0);break;

            case 4: add(b,a,1); if (a==b) flag=1; break;

            case 5: add(a,b,0);break;

        }

    }

    D(i,n,1) add(0,i,1);

    if (flag) {printf("-1\n");return 0;}

    SPFA();

}