/*
* 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 scan=new Scanner(System.in);
int city=scan.nextInt();
int connect=scan.nextInt();
int[][] cities = new int[city+1][2];
int i=1;
while(i<city+1){
cities[i][0]=Integer.MAX_VALUE;
cities[i][1]=Integer.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 < connect; 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(int a:check){
for(int[] k:connections.get(a)){
if(cities[k[0]][0]>k[1]+cities[a][1]){
check2.add(k[0]);
cities[k[0]][0]=k[1]+cities[a][1];
}
}
}
check.clear();
if(check2.isEmpty()){
break;
}
for(int a:check2){
for(int[] k:connections.get(a)){
if(cities[k[0]][1]>cities[a][0]){
check.add(k[0]);
cities[k[0]][1]=cities[a][0]+0;
}
}
}
check2.clear();
}
System.out.println(Math.min(cities[city][0], cities[city][1]));
}
}