#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define PII pair<int, int>
#define IOS cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
#define int long long
#define i64 int64_t
#define PI 3.1415926
typedef unsigned long long ull;
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 9;
// const int p = 131;
const int INF = 0x3f3f3f3f;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// int head[N], ne[N], w[N], ed[N], idx;
int dir[8][2] = {
    {1, 0},
    {0, -1},
    {0, 1},
    {-1, 0},
    {1, -1},
    {-1, -1},
    {-1, 1},
    {1, 1},
};
int in[N];
vector<PII> v[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        in[b]++;
        in[c]++;
        v[a].pb({b, c});
    }
    vector<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (!in[i])
        {
            q.pb(i);
        }
    }
    for (int i = 0; i < q.size(); i++)
    {
        int x = q[i];
        for (auto [y, z] : v[x])
        {
            for (auto a : {y, z})
            {
                if (--in[a] == 0)
                {
                    q.pb(a);
                }
            }
        }
    }
    if (q.size() != n)
    {
        puts("-1");
        return;
    }
    vector<int> a(n + 1, 1);
    for (int i = n - 1; i >= 0; i--)
    {
        int x = q[i];
        for (auto [y, z] : v[x])
        {
            a[x] = max(a[x], a[y] + a[z]);
            if(a[x]>1e9)
            {
                puts("-1");
                return;
            }
        }
    }
    // 5 5
    // 1 2 4
    // 2 5 3
    // 2 4 3
    // 3 5 4
    // 2 5 4
    // for (auto i : a)
    // {
    //     cout << i << ' ';
    // }
    int ans = accumulate(a.begin()+1, a.end(), 0ll);
    if (ans > INF)
    {
        ans = -1;
    }
    cout << ans << endl;
}
signed main()
{
    // IOS;
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }

    //system("pause");
}