#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#define x first
#define y second
#define endl '\n'
#define pi acos(-1.0)
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<int, PII> PIII;
typedef pair<PII, char> PIIC;
typedef long long LL;
int dx[] = {1, 0, 0, -1, -1, -1, 1, 1}, dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
int mou[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int N = 1e6 + 10, M = 50 + 10, mod = 1e9+7, INF = 0x3f3f3f3f;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
int n, m,t;
int e[N],ne[N],h[N],idx,d[N],w[N];
template <typename T>
inline T read()
{
    T x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
LL qmi(LL a, LL b)
{
    LL ans = 1 % mod;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
LL inv(int x)
{
    return qmi(x, mod - 2);
}
LL Random(LL mod)
{
    LL res = INT32_MAX;
    return res * rand() * rand() % mod;
}
int sgn(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}
struct Point
{
    double x, y;
    Point() {}
    Point(double _x, double _y) { x = _x;y = _y; }
    bool operator==(Point b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
    bool operator<(Point b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
    Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
    Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
    // 叉积
    double operator^(const Point &b) const { return x * b.y - y * b.x; }
    // 点积
    double operator*(const Point &b) const { return x * b.x + y * b.y; }
    // 数乘
    Point operator*(const double &k) const {return Point(x * k, y * k);}
    Point operator/(const double &k) const { return Point(x / k, y / k);}
};
struct Line
{
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) { s = _s;e = _e; }
    // ax+by+c=0
    Line(double a, double b, double c)
    {
        if (sgn(a) == 0)
        {
            s = Point(0, -c / b);
            e = Point(1, -c / b);
        }
        else if (sgn(b) == 0)
        {
            s = Point(-c / a, 0);
            e = Point(-c / a, 1);
        }
        else
        {
            s = Point(0, -c / b);
            e = Point(1, (-c - a) / b);
        }
    }
    //`直线和线段相交判断`
    int linecrossseg(Line v)
    {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        if ((d1 ^ d2) == -2) return 2;     //`2 规范相交`
        return (d1 == 0 || d2 == 0);       //`1 非规范相交 0 不相交`
    }
    //`两向量平行(对应直线平行或重合)`
    bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
    //`点在线段上的判断`
    bool pointonseg(Point p) { return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0; }
    //`求两直线的交点  要保证两直线不平行或重合`
    Point crosspoint(Line l)
    {
        Point u = e - s, v = l.e - l.s;
        double t = (s - l.s) ^ v / (v ^ u);
        return s + u * t;
    }
    int relation(Point p)
    {
        int c = sgn((p - s) ^ (e - s));
        if (c < 0) return 1;      //`1  在左侧`
        else if (c > 0) return 2; //`2  在右侧`
        else return 3;            //`3  在直线上`
    }
};

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
vector<PII>rt[N];
bool top()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!d[i]){
            q.push(i);
            w[i]=1;
        }
    if(!q.size()) return false;
    while(q.size()){
        auto t=q.front();q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(!d[j]){
                q.push(j);
                for(auto k:rt[j]){
                    LL t=w[k.x]+w[k.y];
                    if(t>1e9) return false;
                    w[j]=max(w[j],w[k.x]+w[k.y]);
                }
            }
        }
    }
    return true;
}

void solve()
{
    //memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<=2*n+10;i++) h[i]=-1; 
    for(int i=0;i<m;i++){
        int f,a,b;cin>>f>>a>>b;
        add(a,f),add(b,f);
        d[f]+=2;
        rt[f].push_back({a,b});
    }
    if(!top()){
        cout<<-1;
        return;
    }
    LL sum=0;
    for(int i=1;i<=n;i++){
        if(!w[i]){
            cout<<-1;
            return;
        }
        sum+=w[i];
    }
    cout<<sum;
}

int main()
{
    //clock_t start,end;//定义clock_t变量
    //start = clock(); 
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0),cout.precision(10);
    // freopen("in.in","r",stdin);
    // freopen("order.in","w",stdout);
    t = 1; // cin >> t;
    while (t--) solve();
    //end = clock();   //结束时间
    //cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}