#include<bits/stdc++.h>
using namespace std;
int n,m,dis[505][505],dp[505],tmp[505];
struct edge{int u,v,w;}e[125005];
bool cmp(edge x,edge y){return x.w>y.w;}
void cmin(int &x,int y){x=(x<y?x:y);}
int main()
{
	//freopen("fly.in","r",stdin);
	//freopen("fly.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=0x3f3f3f3f;
    for(int i=1;i<=n;i++)dis[i][i]=0;
    for(int i=1;i<=m;i++)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
		dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=1;
	}
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cmin(dis[i][j],dis[i][k]+dis[k][j]);
	sort(e+1,e+m+1,cmp);
	dp[1]=0;for(int i=2;i<=n;i++)dp[i]=0x3f3f3f3f;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)tmp[j]=dp[j];
		int u=e[i].u,v=e[i].v;
		for(int j=1;j<=n;j++)cmin(dp[j],tmp[u]+e[i].w+e[i].w*dis[v][j]);
		for(int j=1;j<=n;j++)cmin(dp[j],tmp[v]+e[i].w+e[i].w*dis[u][j]);
	}
	cout<<dp[n];
	return 0;
}