#include<bits/stdc++.h> using namespace std; int st[20000],dist[20000],n,m,h[20000],c,e[20000],a,b,ne[20000],idx,w[20000]; void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;} void dijkstra(){ memset(dist,0x3f,sizeof(dist)); dist[1]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=1;j<=n;j++)if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j; st[t]=1; for(int j=h[t];j+1;j=ne[j]){ int v=e[j]; dist[v]=min(dist[v],dist[t]+w[j]); } } } int main(){ memset(h,-1,sizeof(h)); cin>>n>>m; for(int i=1;i<=m;i++)cin>>a>>b>>c,add(a,b,c),add(b,a,c); dijkstra(); if(dist[n]==0x3f3f3f3f)cout<<-1; else cout<<dist[n]; return 0; }