#include <bits/stdc++.h>
#define endl '\n'
#define all(a) a.begin(), a.end()
#define ll long long
#define ull unsigned long long
#define inf 0x7fffffff;
//#define int long long
//#define III int
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
//cout << ceil(-0.2) << endl;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll INF = 1e18;

// struct node {
//     ll dis, u;
//     int hh;
//     bool operator>(const node &a) const {return dis > a.dis;}
// };

struct now {
    ll a, b;
    bool operator<(const now& x) const {
        return a < x.a;
    }
};

ll qpow (ll a, ll b) {
    ll ret = 1;
    a %= mod;
    while (b) {
        if (b & 1) {
            ret *= a;
            ret %= mod;
        }
        b /= 2;
        a = (a * a) % mod;
    }
    return ret;
}

ll cmp (ll a, ll b) {
    if (a == 0) return 0;
    if (a > b / 2) a = b - a;
    ll x = 1, y = 1;
    for (int i = 0; i < a; i++) {
        x *= b - i;
        x %= mod;
    }
    for (int i = 1; i <= a; i++) {
        y *= i;
        y %= mod;
    }
    ll ret = x * qpow(y, mod - 2);
    ret %= mod;
    return ret;
}
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

struct node {
    ll w, l, r;
};

// //int n;
// ll tree[500005];
// int lowbit(int x) {
//     return x & (-x);
// }
// void add(int l, ll x) {
//     for (int i = l; i <= n; i += lowbit(i)) {
//         tree[i] += x;
//     }
// }
// ll sum(int r) {
//     ll ret = 0;
//     for (int i = r; i >= 1; i -= lowbit(i)) {
//         ret += tree[i];
//     }
//     return ret;
// }

int n, m;
ll in[200010];
vector<pair<int, int>> g[200010];
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[b].emplace_back(a, c);
        g[c].emplace_back(a, b);
        in[a] += 2;
    }
    queue<int> q;
    vector<ll> ans(n + 1);
    vector<int> flag(n + 1);
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
            ans[i] = 1;
            flag[i] = 1;
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto p : g[u]) {
            if (p.first == u) {
                cout << -1 << endl;
                return;
            }
            ans[p.first] = max(ans[p.first], ans[u] + ans[p.second]);
            in[p.first]--;
            if (in[p.first] == 0) {
                q.push(p.first);
                flag[p.first] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i] == 0) {
            cout << -1 << endl;
            return;
        }
        if (in[i] > 0) {
            cout << -1 << endl;
            return;
        }
    }
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += ans[i];
    }
    cout << sum << endl;
}



int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
    // helper();
    int t = 1;
    //cin >> t;
    while (t--) solve();




    return 0;
}