/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author alexey
*/
import java.util.*;
public class Datatahti201641 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner a=new Scanner(System.in);
int city=io.nextInt();
int connect=scan.nextInt();
long[][] cities = new long[city+1][2];
int i=1;
while(i<city+1){
cities[i][0]=Long.MAX_VALUE;
cities[i][1]=Long.MAX_VALUE;
i++;
}
cities[1][0]=0;
cities[1][1]=0;
ArrayList<ArrayList<int[]>> connections= new ArrayList<ArrayList<int[]>>();
connections.add(new ArrayList());
for (int j = 0; j < city; j++) {
connections.add(new ArrayList<int[]>());
}
for (int j = 0; j < connect; j++) {
int a=scan.nextInt();
int b=scan.nextInt();
int c=scan.nextInt();
int[] d =new int[2];
d[0]=b;
d[1]=c;
connections.get(a).add(d);
}
Set check = new HashSet();
Set check2 = new HashSet();
check.add(1);
while(true){
for(Object b:check){
int a=(Integer) b;
for(int[] k:connections.get(a)){
long x=cities[k[0]][0];
long y=k[1]+cities[a][1];
if(x>y){
check2.add(k[0]);
cities[k[0]][0]=y;
}
}
}
check.clear();
if(check2.isEmpty()){
break;
}
for(Object c:check2){
int a= (Integer) c;
for(int[] k:connections.get(a)){
long x=cities[k[0]][1];
long y=cities[a][0];
if(x>y){
check.add(k[0]);
cities[k[0]][1]=y;
}
}
}
if(check.isEmpty()){
break;
}
check2.clear();
}
io.println(Math.min(cities[city][0], cities[city][1]));
io.close();
}
}