#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pn putchar('\n')
#define maxint 2147483647
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define maxn 505
#define maxm 125005
#define int ll
using namespace std;
struct Gragh
{
    int v,w,nex;
}e[maxm<<1];
struct Dijk
{
    int u,w;
    il bool operator < (const Dijk t) const {return w>t.w;} 
};
int n,m,top;
bool vis[maxn];
int c[maxn],dis[maxn],f[maxn][maxn],g[maxn][maxn],tf[maxn][maxn];
priority_queue<Dijk>q;
il void build_gra(int u,int v,int w)
{
    e[++top]=(Gragh){v,w,c[u]},c[u]=top;
}
il void dijkstra(int pos)
{
    memset(dis,0x3f,sizeof dis);
    dis[pos]=0;
    q.push((Dijk){pos,0});
    while(q.size())
    {
        Dijk t=q.top();q.pop();
        if(vis[t.u])continue;
        vis[t.u]=1;
        for(int i=c[t.u];i;i=e[i].nex)
            if(dis[t.u]+e[i].w<dis[e[i].v])
                dis[e[i].v]=dis[t.u]+e[i].w,q.push({e[i].v,dis[e[i].v]});
    }
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=g[i][j]=tf[i][j]=1e9;
    while(m--)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        f[u][v]=f[v][u]=1;
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    for(int i=1;i<=n;i++)
        f[i][i]=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j]!=1e9)
                for(int k=1;k<=n;k++)
                    if(f[j][k]!=1e9)
                        tf[i][k]=min(tf[i][k],g[i][j]*(f[j][k]+1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(tf[i][j]!=1e9)
                build_gra(i,j,tf[i][j]);
    dijkstra(1);
    printf("%lld",dis[n]);
    return 0;
}