rt

#include <bits/stdc++.h>
#define maxn 1001
#define maxm 100010
using namespace std;
struct node{
	int v,w;
	friend bool operator <(node a,node b){
		return a.w >b.w;
	}
}tmp;
template<typename T>inline void read(T &ff) {
	T rr = 1;
	ff = 0;
	register char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			rr = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		ff = (ff << 1) + (ff << 3) + (ch ^ 48);
		ch = getchar();
	}
	ff *= rr;
}
struct edge{
	int to,nxt,val;
}a[maxm];
int h[maxm],cnt;
void add(int a1,int b,int c){
	a[++cnt].nxt =h[a1];
	a[cnt].to = b;
	a[cnt].val = c;
	h[a1] = cnt;
}
int n,m,ans = 999999999;
int s; //起点
priority_queue<node> q;
int dis[maxm][2];  //dis存两维，一个是起点到终点一个是终点到起点
void dijkstra(int k){ //k代表维度
	dis[s][k] = 0;
	tmp.v = s,tmp.w = 0;
	q.push(tmp);
	while(!q.empty()){
//		cout  << 1 << endl;
		//TODO
		int v = q.top().v,w = q.top().w;
		q.pop();
		if(w != dis[v][k]) continue;
		for(register int i = h[v];i;i = a[i].nxt){
			int to = a[i].to;
			if(dis[to][k] > dis[v][k] + a[i].val){
				dis[to][k] = dis[v][k] + a[i].val;
				tmp.w = dis[to][k],tmp.v = to;
				q.push(tmp);
			}
		}
	}
//	cout << 2 << endl;
}
struct data{ // 存储输入数据
	int x,y,z;
}b[maxm];
int a1,b1,c;
int mi = 1145141919;
int main(){
	memset(dis,0x7f,sizeof(dis));
	cin >> n >> m;
	for(register int i = 1; i <= m; i++){
		read(a1),read(b1),read(c);
		b[i].x = a1,b[i].y = b1,b[i].z = c;
		add(a1,b1,c);
		add(b1,a1,c);
	}
	
//	cout << "ok" << endl;
	s = 1,dijkstra(0);
//	cout << "ok" << endl;
	s = n,dijkstra(1);
	int mx = dis[n][0]; //如果在最短路径（有n个农场）
	int t;
	for(register int i = 1; i <= m; i++){
		int x = b[i].x,y = b[i].y;
		if(dis[x][0] + dis[y][1] > dis[y][0] + dis[x][0]){ //由于分两种情况讨论，因此这里不能加同一条
			t = y;
			y = x;
			x = t;
			//交换原因：因为此时x1y0的组合显然好过x0y1的组合，所以更换	
		}
		if(dis[x][0] + dis[y][1] + b[i].z == mx) continue;
		ans = min(dis[x][0] + dis[y][1] + b[i].z,ans);
	}
	for(register int i = 1; i <= m; i++){
		int x = b[i].x,y = b[i].y;
		if(dis[x][0] + dis[y][1] > dis[y][0] + dis[x][0]){ //由于分两种情况讨论，因此这里不能加同一条
			t = y;
			y = x;
			x = t;
			//交换原因：因为此时x1y0的组合显然好过x0y1的组合，所以更换	
		}
		if(dis[x][0] + dis[y][1] + b[i].z != mx) continue;
		mi = min(b[i].z,mi);
	}
	cout << min(ans,mx + mi * 2);
	return 0;
}