def main
  n,m = gets.chomp.split(' ').map(&:to_i)
  node_list = Array.new(n){ |i| Node.new(i)}

  m.times do
    a,b,c = gets.chomp.split(' ').map(&:to_i)
    edge = Edge.new(node_list[b], c)
    node_list[a].push_edge edge
  end

  some_proc = Proc.new {|a,b|a.cost > b.cost}
  pq = PriorityQueue.new(some_proc)
  pq.enqueue node_list[0]
  until pq.empty? do
    done_node = pq.dequeue
    done_node.done = true
    done_node.next_edges.each do |edge|
      unless edge.next_node.done
        edge.next_node.update_cost(edge.cost+done_node.cost)
        pq.enqueue edge.next_node
      end
    end
  end

  puts node_list[n-1].cost * -1
end


class Node
  def initialize name
    @name = name
    @done = false
    @cost = 0
    @next_edges = []
  end
  
  def push_edge edge
    @next_edges.push edge
  end
  
  def update_cost cost
    @cost = cost if @cost > cost
  end
  
  attr_accessor :done
  attr_reader :name, :cost, :next_edges
end

class Edge
  def initialize next_node, cost
    @next_node = next_node
    @cost = 0 - cost
  end
  
  attr_reader :next_node, :cost
end

class PriorityQueue
  def initialize(compare_proc=nil)
    @heap = []
    if compare_proc.nil?
      @compare_proc = lambda{|a,b| a > b}
    else
      @compare_proc = compare_proc
    end
  end

  private
  def swap(a, b)
    @heap[a],@heap[b] = @heap[b],@heap[a]
  end

  public
  def empty?
    @heap.empty?
  end
  
  def enqueue(data)
    # ????°????????´?
    i = @heap.length
    @heap.push data

    while i > 0
      # ?????????????????´????????????
      parent = (i - 1) / 2

      # ?????????????°???????or??????????????°??????
      break if !@compare_proc.call(@heap[parent], @heap[i])

      # ??????????????§???????????§??\?????????
      swap(parent, i)

      # ?¬??????????????±??????????????????????????????§???i?????´??°
      i = parent
    end
  end

  def dequeue
    if @heap.length <= 1
      return @heap.pop
    end
    
    # ???????????????????????????
    data = @heap[0]

    # ????°??????????????????????????§????
    @heap[0] = @heap.pop

    parent = 0
    while parent * 2 + 1 < @heap.length
      # ???????????????????????????????????¨??\?????????????????????
      a = parent * 2 + 1
      b = parent * 2 + 2
      child = nil
      if b < @heap.length && @compare_proc.call(@heap[a], @heap[b])
        child = b
      else
        child = a
      end

      # ?????§?????????????????¨?????????????????????????°????????????°??????
      break if !@compare_proc.call(@heap[parent], @heap[child])

      # ??????????????§???????????§?????¨??\?????????
      swap(parent, child)

      # ?¬???????????????\???????????????????????¨????????????
      parent = child
    end

    data
  end

  def first
    @heap.first
  end
end

main