#include<cstdio>

 #include<iostream>

 using namespace std;

 int n,m,cnt,head[],next[],u[],v[],h,t,a[];

 int ci[],f[];

 long long d[];

 void jia(int a1,int a2,int a3)

 {

     cnt++;

     next[cnt]=head[a1];

     head[a1]=cnt;

     u[cnt]=a2;

     v[cnt]=a3;

 }

 int main()

 {

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

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

       {

         int a1,a2,a3;

         scanf("%d%d%d",&a1,&a2,&a3);

         if(a1==)

           {

             jia(a2,a3,);

             jia(a3,a2,);

             }

         if(a1==)

         {if(a2==a3){printf("-1");return ;}

           jia(a2,a3,);}

         if(a1==)

           jia(a3,a2,);

         if(a1==)

         {if(a2==a3){printf("-1");return ;}

           jia(a3,a2,);}

         if(a1==)

           jia(a2,a3,);

       }

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

       jia(,i,);

     a[]=;

     ci[]++;

     t=;

     f[]=;

     for(;h!=t;)

       {

         h++;

         if(h>)

         h=;

         f[a[h]]=;

         for(int i=head[a[h]];i;i=next[i])

           if(d[u[i]]<d[a[h]]+v[i])

             {

                 d[u[i]]=d[a[h]]+v[i];

                 ci[u[i]]++;

                 if(ci[u[i]]==n+)

                   {

                     printf("-1\n");

                     return ;

                     }

                 if(!f[u[i]])

                   {

                     t++;

                     if(t>)

                       t=;

                     a[t]=u[i];

                     f[u[i]]=;

                   }

               }

       }

     long long ans=;

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

       ans+=d[i];

     printf("%lld",ans);

     return ;

 }