#include<bits/stdc++.h>
using namespace std;
int n,r;
long long ans[2][5001];
bool vis[5001];
struct node{int v,w;};
bool operator<(node a,node b){
	return a.w<b.w;
}
vector<node>a[5001];
queue<int>q;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>r;
	for(int i=1,u,v,w;i<=r;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	q.push(1);vis[1]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		sort(a[u].begin(),a[u].end());
		if(u==1)ans[1][u]=a[u][0].w<<1;//起点的次短路是一来一回 
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].v,w=a[u][i].w,c=w+ans[0][u];
			if(!vis[v]){//新的农场 
				vis[v]=1;
				ans[0][v]=c;
				q.push(v);
			}
			else if(c<ans[0][v]){//更新最短路 
				ans[1][v]=ans[0][v];
				ans[0][v]=c;
				q.push(v);
			}
			else if(c<ans[1][v]&&c>ans[0][v]){//更新次短路 
				ans[1][v]=c;
				q.push(v);
			}
			if(!ans[1][v]){
				ans[1][v]=w+ans[1][u];
				q.push(v);
			}
		}
		ans[1][u]=min(ans[1][u],ans[0][u]+a[u][0].w*2);
	}
	cout<<ans[1][n];
	return 0;
}
/*3743 3659*/

rt，没查出错望指教。