package Main;
import java.util.*;
public class Main {
public static void main(String[] args) {
IO io = new IO();
int cityAmount = io.nextInt();
int flights = io.nextInt();
ArrayList<City> cities = new ArrayList<>();
for (int i = 1; i <= cityAmount; i++) {
cities.add(new City(i));
}
for (int i = 0; i < flights; i++) {
cities.get(io.nextInt()-1).neighbours.add(new Flight(cities.get(io.nextInt()-1),io.nextInt()));
}
flightCosts(cities.get(0));
System.out.println(cities.get(cityAmount-1).minDistance);
}
public static void flightCosts(City source) {
Boolean isFree = false;
source.minDistance = 0;
PriorityQueue<City> cityList = new PriorityQueue<City>();
cityList.add(source);
while (!cityList.isEmpty()) {
City c = cityList.poll();
for (Flight flight : c.neighbours) {
City v = flight.target;
int cost = 0;
if (!isFree) {
cost = flight.cost;
}
int newCost = c.minDistance + cost;
if (newCost < v.minDistance) {
cityList.remove(v);
v.minDistance = newCost;
cityList.add(v);
}
}
isFree = !isFree;
}
}
}
class City {
public int name;
public ArrayList<Flight> neighbours;
public int minDistance = Integer.MAX_VALUE;
public City(int name) {
this.name = name;
neighbours = new ArrayList<>();
}
public int compareTo(City other) {
return Integer.compare(minDistance, other.minDistance);
}
}
class Flight {
public City target;
public int cost;
public Flight(City target, int cost) {
this.target = target;
this.cost = cost;
}
}