#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n + 1);
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        v[x].emplace_back(y);
        v[x].emplace_back(z);
        g[x].emplace_back(y, z);
    }

    for (int i = 1; i <= n; i++)
        sort(v[i].begin(), v[i].end());

    for (int i = 1; i <= n; i++)
    {
        for (const int &nei : v[i])
        {
            if (binary_search(v[nei].begin(), v[nei].end(), i))
            {
                cout << -1 << "\n";
                return;
            }
        }
    }

    bool isok = true;

    vector<i64> ans(n + 1);

    function<void(int)> dfs = [&](int x) {
        if (ans[x])
            return;
        i64 mx = 1;
        for (auto [y, z] : g[x])
        {
            dfs(y);
            dfs(z);
            mx = max(mx, ans[y] + ans[z]);
        }
        ans[x] = mx;
        if (ans[x] > 1e9)
            isok = false;
    };

    for (int i = 1; i <= n; i++)
        dfs(i);

    if (!isok)
    {
        cout << -1 << "\n";
        return;
    }
    i64 res = accumulate(ans.begin() + 1, ans.begin() + n + 1, 0LL);
    if (res > 1e9)
    {
        cout << -1 << "\n";
        return;
    }
    cout << res << "\n";
}

int main()
{
#ifdef lijn
    freopen("/home/lijn/acm_practice/.build/input.in", "r", stdin);
    freopen("/home/lijn/acm_practice/.build/output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}