include <bits/stdc++.h>

using namespace std; struct pi { long long d,r,x; bool operator <(const pi& other) const { return d>other.d; } }; int n,m,u,v,w,kc,num; long long dis[200005][2]; vector<pair<int,int>>ke[2000005]; void dijkstra() { for(int i=1;i<=n;i++)dis[i][0]=dis[i][1]=1e18; dis[1][0]=0; priorityqueue<pi>pq; pq.push({dis[1][0],0,0}); while(pq.size()) { u=pq.top().x; kc=pq.top().d; num=pq.top().r; pq.pop(); if(kc>dis[u][num])continue; for(pair<int,int> it:ke[u]) { v=it.first; w=it.second; if(kc+w>dis[v][0]) { dis[v][1]=dis[v][0]; dis[v][0]=kc+w; pq.push({dis[v][0],0,v}); } else if(kc+w>dis[v][1]&&kc+w<dis[v][0]) { dis[v][1]=kc+w; pq.push({dis[v][1],1,v}); } } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u>>v>>w; ke[u].pushback({v,w}); ke[v].push_back({u,w}); } dijkstra(); if(dis[n][2]==1e18)cout<<-1; else cout<<dis[n][2]; }