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