#include <stdio.h>
#include <vector>
#include <stdlib.h>

using namespace std;

#define maxv 10010
#define pb push_back
#define minim(a,b) (a < b ? a : b)
#define maxn 110

int n,m,cost,l;
vector <int> a[maxn],c[maxn];
int sol[maxn],g[maxn],s[maxn];

void BFS()
{
     int i,j,aux;
     l=1;
     s[1]=1;
     
     for (i=1;i<=n;i++) sol[i]=maxv;
     
     for (i=1;i<=l;i++)
       for (j=0;j<g[s[i]];j++) 
       {
           aux=minim(sol[s[i]],c[s[i]][j]);
           if (aux<sol[a[s[i]][j]]) 
           {
               s[++l]=a[s[i]][j];
               sol[s[l]]=aux;
           }
       }
}

int main()
{
    freopen("flux.in","r",stdin);
    freopen("flux.out","w",stdout);
    
    scanf("%d %d ",&n,&m);
    
    int i,x,y,z;
    
    if (m==n-1) 
    {
       for (i=1;i<=m;i++) 
       {
           scanf("%d %d %d ",&x,&y,&z);
           z=abs(z);
           a[x].pb(y);
           a[y].pb(x);
           c[x].pb(z);
           c[y].pb(z);   
       }
       
       for (i=1;i<=n;i++) g[i]=a[i].size();
       
       BFS();
       
       printf("%d ",sol[n]);
       
       return 0;
    }
    
    int min=maxv;
    
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d ",&x,&y,&z);
        z=abs(z);
        if ((x==n) || (y==n))
        {
            cost++;
            if (z<min) min=z;
        }
    }
    
    printf("%d\n",cost*min);
    
    return 0;
}