#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
using ull=unsigned long long;
const long long inf=0x3f3f3f3f3f3f3f3f;
using i128=__int128;
const int mod=1000000007;
const long double eps=0.00000000001;

struct DSU
{
    vector<int>f,siz;
    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while(x!=f[x])
        {
            x=f[x]=f[f[x]];
        }
        return x;
    }

    bool same(int x, int y)
    {
        return find(x)==find(y);
    }

    bool merge(int x,int y)
    {
        x=find(x);
        y=find(y);
        if(x==y)
        {
            return false;
        }
        siz[x]+=siz[y];
        f[y]=x;
        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};

vector<pair<int,int>>a[200010];
i128 ans[200010];
DSU c{200010};
int f=0;

void dfs(int p)
{
    if(f==-1)return;
    if(a[p].empty())
    {
        ans[p]=1;
        return;
    }
    int la=(int)a[p].size();
    i128 mx=-inf;
    for(int i=0;i<=la-1;i++)
    {
        int x=a[p][i].first;
        int y=a[p][i].second;
        if(ans[x]==-1)dfs(x);
        if(ans[y]==-1)dfs(y);
        mx=max(mx,ans[x]+ans[y]);
    }
    if(mx>1000000000)f=-1;
    else ans[p]=mx;
}


void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)ans[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x==y||x==z)f=-1;
        int fax=c.find(x);
        if(fax==y)f=-1;
        if(fax==z)f=-1;
        if(f!=-1)
        {
            c.merge(x,y);
            c.merge(x,z);
            a[x].push_back({y,z});
        }
        else continue;
    }
    if(f==-1)
    {
        printf("-1\n");
        return;
    }
    vector<int> rt;
    for(int i=1;i<=n;i++)
    {
        if(c.f[i]==i)
        {
            rt.push_back(i);
        }
    }
    ll lr=(ll)rt.size();
    for(ll i=0;i<=lr-1;i++)
    {
        if(ans[rt[i]]==-1)dfs(rt[i]);
        if(f==-1)
        {
            printf("-1\n");
            return;
        }
    }
    i128 sum=0;
    for(ll i=1;i<=n;i++)
    {
        sum+=ans[i];
        if(sum>1000000000)
        {
            printf("-1\n");
            return;
        }
    }
    printf("%lld\n",(ll)sum);
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    ll _=1;
//    cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}