#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=505;
int n,m,g[N][N],dis[N][N],dis2[N],vis[N];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	For(i,1,m){
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	memset(dis,0x3f,sizeof(dis));
	For(i,1,n){
		For(j,1,n){
			if(g[i][j]<1e9){
				dis[i][j]=1;
			}
		}
		dis[i][i]=0;
	}
	For(k,1,n){
		For(i,1,n){
			For(j,1,n){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	memset(dis2,0x3f,sizeof(dis2));
	dis2[1]=0;
	For(_,1,n){
		int u=0;
		For(i,1,n){
			if(!vis[i]&&(!u||dis2[i]<dis2[u])){
				u=i;
			}
		}
		if(!u) break;
		vis[u]=1;
		For(v,1,n){
			if(g[u][v]<1e9){
				For(x,1,n){
					if(dis[v][x]<1e9){
						dis2[x]=min(dis2[x],dis2[u]+g[u][v]*(dis[v][x]+1));
					}
				}
			}
		}
	}
	cout<<dis2[n]<<'\n';
	return 0;
}