#include<bits/stdc++.h> using namespace std; const int N=2010,M=10010; int e[M],ne[M],h[N],w[M],idx,dis[N],st[N],n,m; void add(int a,int b,int c){ e[idx]=b; ne[idx]=h[a]; w[idx]=c; h[a]=idx++; } int D(){ 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(!st[j]&&(t==-1||dis[t]>dis[j])) t=j; } st[t]=1; for(int j=h[t];j!=-1;j=ne[j]){ dis[e[j]]=min(dis[e[j]],dis[t]+w[j]); } } if(dis[n]==0x3f3f3f3f) return -1; return dis[n]; } int main(){ cin>>n>>m; memset(h,-1,sizeof(h)); int a,b,c; for(int i=1;i<=m;i++){ cin>>a>>b>>c; add(a,b,c);add(b,a,c); } cout<<D()<<endl; return 0; }