#include<bits/stdc++.h>
using namespace std;
const int N=105;
int mem[N],a[N][N],ans=INT_MAX,n,m;
bool book[N];
struct node{
int x,sum;//表示到了第x个点，路费为sum
}now,ne;
queue<node> q;
void bfs(int x){
now.x=x,now.sum=0;
q.push(now);
while(!q.empty()){
now=q.front();
if(now.x==n) ans=min(ans,now.sum);
for(int i=1;i<=n;i++){
if(mem[i]<now.sum+a[now.x][i]) continue;//剪枝
if(a[now.x][i]!=-1){
ne.x=i,ne.sum=now.sum+a[now.x][i];
mem[i]=ne.sum;
q.push(ne);
}
}
q.pop();
}
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(mem,0x3f,sizeof mem);//初始化
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=-1;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z;//存储图
}
book[1]=1;//将起点标记为1
bfs(1);
cout<<ans;
return 0;
}
