#include<bits/stdc++.h>

using namespace std;

#define MAXN 100010

struct Edge

{

        int to;

        long long w;

        int nxt;

} e[MAXN<<];

int x,a,b,i,n,k,tot;

long long dis[MAXN];

int head[MAXN];

template <typename T> inline void read(T &x)

{

    int f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

template <typename T> inline void write(T x)

{

    if (x < )

    {

        putchar('-');

        x = -x;

    }

    if (x > ) write(x/);

    putchar(x%+'');

}

template <typename T> inline void writeln(T x)

{

    write(x);

    puts("");

}

inline void add(int u,int v,long long w)

{

        tot++;

        e[tot] = (Edge){v,w,head[u]};

        head[u] = tot;

}

inline long long spfa()

{

        int i,cur,v;

        long long w,ans = ;

        queue<int> q;

        static bool inq[MAXN];

        static int cnt[MAXN];

        q.push();

        inq[] = true;

        cnt[] = ;

        while (!q.empty())

        {

                cur = q.front();

                q.pop();

                inq[cur] = false;

                for (i = head[cur]; i; i = e[i].nxt)

                {

                        v = e[i].to;

                        w = e[i].w;

                        if (dis[cur] + w > dis[v])

                        {

                                dis[v] = dis[cur] + w;

                                if (!inq[v])

                                {

                                        inq[v] = true;

                                        q.push(v);

                                        cnt[v]++;

                                        if (cnt[v] > n) return -;

                                }

                        }

                }

        }

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

        return ans;

}

int main()

{

        read(n); read(k);

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

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

        {

                read(x); read(a); read(b);

                if (x == )

                {

                        add(a,b,);

                        add(b,a,);

                }

                if (x == )

                {

                        add(a,b,);

                        if (a == b)

                        {

                                writeln(-);

                                return ;

                        }

                }

                if (x == ) add(b,a,);

                if (x == )

                {

                        add(b,a,);

                        if (a == b)

                        {

                                writeln(-);

                                return ;

                        }

                }

                if (x == ) add(a,b,);

        }

        writeln(spfa());

        return ;

}