#include <iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
int dist[N];
int n, m;
typedef pair<int, int>pii;
bool st[N];
int cnt[N];
vector<pii>q[N];
bool spfa()
{
    memset(dist, -0x3f3f3f, sizeof(dist));
    queue<int>qq;
    qq.push(0);
    dist[0] = 0;
    st[0] = true;
    while (qq.size())
    {
        int t = qq.front();
        qq.pop();
        st[t] = true;
        for (int i = 0; i < q[t].size(); i++)
        {
            int v = q[t][i].first, w = q[t][i].second;
            if (dist[v] < dist[t] + w)
            {
                dist[v] = dist[t] + w;
                cnt[v] = cnt[t] + 1;
                if (cnt[v] >= n+m)return false;               
                qq.push(v);
                st[v] = true;           
            }
        }
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int num1, num2, num3;
        cin >> num1 >> num2 >> num3;
        if (num1 == 1)
        {
            q[num2].push_back(make_pair(num3, 0));
            q[num3].push_back(make_pair(num2, 0));
        }
        else if (num1 == 2)q[num2].push_back(make_pair(num3, 1));
        else if (num1 == 3)q[num2].push_back(make_pair(num3, 0));
        else if (num1 == 4)q[num3].push_back(make_pair(num2, 1));
        else if (num1 == 5)q[num2].push_back(make_pair(num3, 0));
    }
    for (int i = 1; i <= n; i++)
    {
        q[0].push_back(make_pair(i,1));
    } 
    bool ty = spfa();
    if (ty)
    {
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ans += dist[i];
        } 
        cout << ans << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}