#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e3+100;
struct edge {
	int v, w;
};
struct Node {
	int dis, u;
	bool operator>(const Node& a) const { return dis > a.dis; }
};
vector<edge> e[MAXN];
int dis[MAXN],dis2[MAXN],vis[MAXN];
priority_queue<Node, vector<Node>, greater<Node>> q;
void dijkstra(int s) {
	memset(dis, 0x3f,sizeof(dis));
	memset(dis2, 0x3f,sizeof(dis2));
	memset(vis, 0, sizeof(vis));
	dis[s] = 0;
	dis2[s]=0;
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().u;
		int va=q.top().dis;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto ed : e[u]) {
			int v = ed.v, w = ed.w;
			if (dis[v] > va + w) {
				dis2[v]=dis[v];
				dis[v] = va + w;
				q.push({dis[v], v});
				q.push({dis2[v],v});
			}
			else if(dis2[v]>va + w){
				dis2[v]= va + w;
				q.push({dis2[v],v});
			}
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,t;
		cin>>a>>b>>t;
		e[a].push_back(edge{b,t});
		e[b].push_back(edge{a,t});
	}
	dijkstra(1);
	cout<<dis2[n]<<endl;
	return 0;
}