#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#define N 10000000

using namespace std;

int n,k,tot,head[N];

long long ans;

struct node{

    int to,next,w;

}e[N];

void add(int u,int v,int w){

    e[++tot].to=v,e[tot].next=head[u],head[u]=tot,e[tot].w=w;

}

int d[N],in[N];

struct npdE{

    int to,dis;

    bool operator < (npdE x)const{

        return dis>x.dis;

    }

};

queue<npdE>Q;

bool vis[N];

void spfa(){

    Q.push((npdE){,});

    vis[]=;

    while(!Q.empty()){

        int u=Q.front().to;vis[u]=,Q.pop();

        if(in[u]>n) {

            printf("-1");return;

        }

        for(int i=head[u];i;i=e[i].next){

            int v=e[i].to;

            if(d[v]<d[u]+e[i].w){

                d[v]=d[u]+e[i].w;

                if(!vis[v]) in[v]=in[u]+,vis[v]=,Q.push((npdE){v,d[v]});

            }

        }

    }

    for(int i=;i<=n;i++) ans+=d[i];

    printf("%lld\n",ans);

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int x,u,v,i=;i<=k;i++){

        scanf("%d%d%d",&x,&u,&v);

        if(x==) add(u,v,),add(v,u,);

        else if(x==) add(u,v,);

        else if(x==) add(v,u,);

        else if(x==) add(v,u,);

        else add(u,v,);

        if(x==||x==) if(u==v) {return puts("-1"),;}

    }

    for(int i=n;i>=;i--) add(,i,);

    spfa();

    return ;

}