using System;

using System.Collections.Generic;

using System.Linq;

public class Result {

    public static int minCost(int gNodes, List<int> gFrom, List<int> gTo, List<int> gWeight) {

        var graph = new List<Tuple<int, int>>[gNodes];

        var mset = new HashSet<int>[gNodes];

        var distances = new int[gNodes];

        for (int i = 0; i < gNodes; ++i) {

            graph[i] = new List<Tuple<int, int>>();

            mset[i] = new HashSet<int>();

        }

        for (int i = 0; i < gFrom.Count;++i) {

            --gFrom[i];

            --gTo[i];

            graph[gFrom[i]].Add(new Tuple<int, int>(gTo[i], gWeight[i]));

            mset[gFrom[i]].Add(gTo[i]);

        }

        distances[0] = 0;

        var notRelaxed = new SortedSet<Tuple<int, int>>();

        notRelaxed.Add(new Tuple<int, int>(0, 0));

        for (int i = 0; i < gNodes; ++i) {

            if (i != 0) {

                distances[i] = int.MaxValue;

                notRelaxed.Add(new Tuple<int, int>(int.MaxValue, i));

            }

            for (int j = 0; j < gNodes; ++j) {

                if (!mset[i].Contains(j))

                    graph[i].Add(new Tuple<int, int>(j, 1));

            }

        }

        while (notRelaxed.Count != 0) {

            var currentMin = notRelaxed.Min;

            notRelaxed.Remove(currentMin);

            var vertex = currentMin.Item2;

            foreach(var edge in graph[vertex]) {

                if (distances[edge.Item1] > distances[vertex] + edge.Item2) {

                    notRelaxed.Remove(new Tuple<int, int>(distances[edge.Item1], edge.Item1));

                    distances[edge.Item1] = distances[vertex] + edge.Item2;

                    notRelaxed.Add(new Tuple<int, int>(distances[edge.Item1], edge.Item1));

                }

            }

        }

        return distances[gNodes - 1];

    }

    public static void Main() {

        var inarr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        int nodes = inarr[0];

        int edges = inarr[1];

        var gFrom = new List<int>();

        var gTo = new List<int>();

        var gWeight = new List<int>();

        for (int i = 0; i < edges; ++i) {

            var minarr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            gFrom.Add(minarr[0]);

            gTo.Add(minarr[1]);

            gWeight.Add(minarr[2]);

        }

        Console.WriteLine(minCost(nodes, gFrom, gTo, gWeight));

    }

}