#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

queue<int>q;

int const MAXN=1e5+;

int n,k,head[MAXN],ct,dis[MAXN],cnt[MAXN];

bool in[MAXN];

long long ans;

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[MAXN<<];

bool spfa(int s)

{

    memset(in,,sizeof in);

    memset(dis,-,sizeof dis);

    dis[s]=;in[s]=;q.push(s);cnt[s]=;

    while(q.size())

    {

        int x=q.front();q.pop();in[x]=;

        for(int i=head[x],u;i;i=edge[i].next)

        {

            if(dis[u=edge[i].to]<dis[x]+edge[i].w)

            {

                if(++cnt[u]>=n)return ;

                dis[u]=dis[x]+edge[i].w;

                if(!in[u])in[u]=,q.push(u);

            }

        }

    }

    return ;

}

int main()

{

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

    int tp,x,y;

    for(int i=;i<=k;i++)

    {

        scanf("%d%d%d",&tp,&x,&y);

        if(tp==){edge[++ct]=N(y,head[x],),head[x]=ct;

                  edge[++ct]=N(x,head[y],),head[y]=ct;}

        if(tp==){if(x==y){printf("-1");return ;}

            else edge[++ct]=N(y,head[x],),head[x]=ct;}

        if(tp==)edge[++ct]=N(x,head[y],),head[y]=ct;

        if(tp==){if(x==y){printf("-1");return ;}

            else edge[++ct]=N(x,head[y],),head[y]=ct;}

        if(tp==)edge[++ct]=N(y,head[x],),head[x]=ct;

    }

    for(int i=n;i;i--)

        edge[++ct]=N(i,head[],),head[]=ct;

    if(!spfa())

    {

        printf("-1");return ;

    }

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

    printf("%lld",ans);

    return ;

}