#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<set<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;
        if (v[y].count(x) || v[z].count(x))
        {
            cout << -1 << "\n";
            return;
        }
        v[x].insert(y);
        v[x].insert(z);
        g[x].emplace_back(y, z);
    }
    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;
    };

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

    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();
}