require 'set'
loop do
    n, m = gets.split.map(&:to_i)
    break if n == 0
    g = {}
    (1..n).each {|i| g[i] = {}}
    m.times do
        a, b, f = gets.split.map(&:to_i)
        g[a][b] = f
    end
    start_node = [1, 1]
    nodes = Set[start_node]
    cost = Hash.new(Float::INFINITY)
    cost[start_node] = 0
    reached = Set.new
    loop do
        u = nodes.min_by {|v| cost[v]}
        nodes.delete(u)
    #     reached << u
    #     i, ticket = u
    #     if i == n
    #         puts cost[u]
            break
    #     end
    #     if ticket == 1
    #         g[i].each do |j, _|
    #             g[j].each do |k, _|
    #                 v = [k, 0]
    #                 if !reached.include?(v)
    #                     cost[v] = cost[u] if cost[v] > cost[u]
    #                     nodes << v
    #                 end
    #             end
    #         end
    #     end
    #     g[i].each do |j, f|
    #         v = [j, ticket]
    #         if !reached.include?(v)
    #             cost[v] = cost[u] + f if cost[v] > cost[u] + f
    #             nodes << v
    #         end
    #     end
    end
end

