using System.Linq;
using static System.Math;
using System.Collections.Generic;
using System;

public class Node
{
    public List<int> from { get; set; }
    public List<int> fromc { get; set; }
    public List<int> to { get; set; }
    public List<int> toc { get; set; }
    public int[] d { get; set; }
    public int count1 { get; set; }
    public int count2 { get; set; }
}

public class P
{
    public int to { get; set; }
    public int c { get; set; }
}

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var m = int.Parse(line[1]);
        var nodes = new Node[n];
        for (int i = 0; i < n; i++) nodes[i] = new Node { from = new List<int>(), to = new List<int>(), d = new int[] { 0, int.MaxValue }, fromc = new List<int>(), toc = new List<int>() };
        for (int i = 0; i < m; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            var a = int.Parse(line[0]);
            var b = int.Parse(line[1]);
            var c = int.Parse(line[2]);
            nodes[a].to.Add(b);
            nodes[a].toc.Add(c);
            nodes[b].from.Add(a);
            nodes[b].fromc.Add(c);
        }
        getData1(nodes, n, m);
        Console.WriteLine(nodes[n-1].d[0]);
    }
    static void getData2(Node[] nodes, int n, int m)
    {
        nodes[n - 1].d[1] = nodes[n - 1].d[0];
        var q = new Queue<P>();
        for (int i = 0; i < nodes[n - 1].from.Count(); i++)
            q.Enqueue(new P { to = nodes[n - 1].from[i], c = nodes[n - 1].d[0] - nodes[n - 1].fromc[i] });
        while (q.Count() > 0)
        {
            var w = q.Dequeue();
            nodes[w.to].d[1] = Min(nodes[w.to].d[1], w.c);
            nodes[w.to].count2++;
            if (nodes[w.to].count2 == nodes[w.to].to.Count())
            {
                for (int i = 0; i < nodes[w.to].from.Count(); i++)
                    q.Enqueue(new P { to = nodes[w.to].from[i], c = nodes[w.to].d[1] - nodes[w.to].fromc[i] });
            }
        }
    }
    static void getAns(Node[] nodes, int n)
    {
        var q = new Queue<P>();
        for (int i = 0; i < nodes[0].to.Count(); i++)
            q.Enqueue(new P { to = nodes[0].to[i], c = nodes[0].toc[i] });
        while (q.Count() > 0)
        {
            var w = q.Dequeue();
            Console.WriteLine("to= {0} c = {1}", w.to, w.c);
            if (w.to == n - 1) { Console.WriteLine(w.c); break; }
            if (nodes[w.to].d[1] - nodes[w.to].d[0] == 0)
                for (int i = 0; i < nodes[w.to].to.Count(); i++)
                    q.Enqueue(new P { to = nodes[w.to].to[i], c = nodes[w.to].toc[i] + w.c });
        }
    }
    static void getData1(Node[] nodes, int n, int m)
    {
        var q = new Queue<P>();
        for (int i = 0; i < nodes[0].to.Count(); i++)
            q.Enqueue(new P { to = nodes[0].to[i], c = nodes[0].toc[i] });
        while (q.Count() > 0)
        {
            var w = q.Dequeue();
            nodes[w.to].d[0] = Max(nodes[w.to].d[0], w.c);
            nodes[w.to].count1++;
            if (nodes[w.to].count1 == nodes[w.to].from.Count())
            {
                for (int i = 0; i < nodes[w.to].to.Count(); i++)
                {
                    q.Enqueue(new P { to = nodes[w.to].to[i], c = nodes[w.to].toc[i] + nodes[w.to].d[0] });
                }
            }
        }
    }
}



Measured memory_bytes: 20628