//注:输入数据在文件中
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;
#define N 100
int ans[N];
struct E{//邻接表结构体
int next;
int cost;
};
bool mark[N];
int dis[N];
vector<E> T[N];
int sum=0;//统计总的结点个数
int main(){
for(int k=1;k<N;k++){dis[k]=-1;mark[k]=false;}
FILE *fp1,*fp2;
fp1=fopen("1.in","r");
fp2=fopen("1.out","w");
int m,n;
fscanf(fp1,"%d%d",&n,&m);
while(m--){
int a,b,c;
fscanf(fp1,"%d%d%d",&a,&b,&c);
E temp;
temp.next=b;
temp.cost=c;
T[a].push_back(temp);
temp.next=a;
T[b].push_back(temp);
}
dis[1]=0;//到自己的距离设置为0
mark[1]=true;//将结点1加入集合中
int newp=1;//新加入的结点为1
for(int j=1;j<n;j++){////循环n-1次确定结点1到其它各个结点的距离,这个循环是确定单源点和最新加入最短路径结点集合的点的邻接点(并且邻接点///未加入最短路径结点集合)
for(int k=0;k<T[newp].size();k++){
int t=T[newp][k].next;
int c=T[newp][k].cost;
if(mark[t]==true)continue;
if(dis[t]>dis[newp]+c||dis[t]==-1){
dis[t]=dis[newp]+c;
}
}
int min=123123;
for(int l=1;l<=n;l++){
if(mark[l]==true)continue;
if(dis[l]==-1)continue;
if(min>dis[l]){min=dis[l];newp=l;}
}
mark[newp]=true;
}
fprintf(fp2,"%d",dis[n]);
return 0;
}