rt

// 最短路
// 我的思路是通过变形成v<=u+w的形式w∈(0,-1)这样先满足小朋友的相对关系
// 然后添加超级零点保证联通性 s->u (0) 这条边实际上也是一个约束 相当于u<=s(0)+0（s是0是因为s只有出边所以s会保持原始值） 会导致所有节点 u<=0
// 这时候通过差分的平移不变性 给每个节点加上一个值 来保证u>=1
// 但是卡spfa。。。
// magic 用来防止spfa超时 神秘小优化

# include <bits/stdc++.h>
using namespace std;
# define INF LLONG_MAX

vector<pair<int,int>> e[100005];
long long n,m,ans;
long long dist[100005];
bool inq[100005];
int cnt[100005];
int magic;
void spfa(){
    fill(dist,dist + 100005,INF); 
    dist[0]=0;
    queue <int> q;
    q.push(0);
    inq[0]=true; 
    while (!q.empty()){
        int u = q.front();
        q.pop(); inq[u] = false;
        //if (++magic > 1e7) {cout << -1; return;}
        for (auto edge : e[u]){
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] > n){
                    cout << -1;
                    return;
                }
                if (!inq[v]){
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    long long themin = INF;
    for(int i = 1; i <= n; i++){
        themin = min(themin,dist[i]);
    }
    for (int i = 1; i <= n; i++){
        ans += dist[i] + (1 - themin);       //保证最小值大于1；
    }
    cout << ans;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x,a,b;
        cin >> x >> a >> b;
        switch (x){
            case 1:
                e[b].push_back({a,0});
                e[a].push_back({b,0});
                break;
            case 2:
                e[b].push_back({a,-1});
                break;
            case 3:
                e[a].push_back({b,0});
                break;
            case 4:
                e[a].push_back({b,-1});
                break;
            case 5:
                e[b].push_back({a,0});
                break;
        }
    }
    for (int i = 1; i <= n; i++){
        e[0].push_back({i,-INF});
    }
    spfa();
    return 0;
}

// // 最长路
// // 可以变形成v>=u+w∈（0,1） 发现这是最长路的形式
// // 而spfa只要把松弛条件反过来变成 v < u+w 就是最长路 （正确性易证）
// // 而且对于 u >= 1 的条件，可以直接从超级零点引一条1的出边 相当于 u >= s(0) + 1
// // 刚好可以避免平移的操作
// // magic 用来防止spfa超时 神秘小优化

// # include <bits/stdc++.h>
// using namespace std;
// # define INF LLONG_MAX

// vector<pair<int,int>> e[100005];
// long long n,m,ans;
// long long dist[100005];
// bool inq[100005];
// int cnt[100005];
// int magic;
// void spfa(){
//     fill(dist,dist + 100005,-INF);
//     dist[0]=0;
//     queue <int> q;
//     q.push(0);
//     inq[0]=true; 
//     while (!q.empty()){
//         int u = q.front();
//         q.pop(); inq[u] = false;
//         if (++magic > 1e7) {cout << -1; return;}
//         for (auto edge : e[u]){
//             int v = edge.first;
//             int w = edge.second;
//             if (dist[v] < dist[u] + w){
//                 dist[v] = dist[u] + w;
//                 cnt[v] = cnt[u] + 1;
//                 if (cnt[v] > n){
//                     cout << -1;
//                     return;
//                 }
//                 if (!inq[v]){
//                     q.push(v);
//                     inq[v]=true;
//                 }
//             }
//         }
//     }
//     for (int i = 1; i <= n; i++){
//         ans += dist[i];       //保证最小值大于1；
//     }
//     cout << ans;
// }

// int main() { 
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cin >> n >> m;
//     for (int i = 1; i <= m; i++){
//         int x,a,b;
//         cin >> x >> a >> b;
//         switch (x){
//             case 1:
//                 e[b].push_back({a,0});
//                 e[a].push_back({b,0});
//                 break;
//             case 2:
//                 e[a].push_back({b,1});
//                 break;
//             case 3:
//                 e[b].push_back({a,0});
//                 break;
//             case 4:
//                 e[b].push_back({a,1});
//                 break;
//             case 5:
//                 e[a].push_back({b,0});
//                 break;
//         }
//     }
//     for (int i = 1; i <= n; i++){
//         e[0].push_back({i,1});
//     }
//     spfa();
//     return 0;
// }