class Log
  def initialize(enabled)
    @enabled = enabled
    @file = File.open("logA.txt", "wb") if @enabled
  end
  def close
    @file.close if @enabled
  end
  def print(str)
    @file.print(str) if @enabled
  end
end

class Simulation
  def initialize
    @point = 0
    @time = 0
    @order_list = []
    @depot_order = []
    @load = []
    @curr_v = 1
    @next_v = -1
    @way_len = 0
    @distance = 0
    
    #@log = Log.new(true)
    @log = Log.new(false)
  end
  
  def read_graph
    @n_vertex, @n_edge = gets.split.map(&:to_i)
    @edges = (@n_vertex + 1).times.map { Array.new((@n_vertex + 1), -1) }
    @min_len = (@n_vertex + 1).times.map { Array.new((@n_vertex + 1), 1000000) }
    for i in 1...(@n_vertex + 1) do
      @min_len[i][i] = 0
    end
    for i in 0...@n_edge do
      u, v, d = gets.split.map(&:to_i)
      @edges[u][v] = d
      @edges[v][u] = d
      @min_len[u][v] = d
      @min_len[v][u] = d
    end
    
    # Warshall-Floyd
#    for k in 1...(@n_vertex + 1) do
#      for i in 1...(@n_vertex + 1) do
#        for j in 1...(@n_vertex + 1) do
#          @min_len[i][j] = [@min_len[i][j], @min_len[i][k] + @min_len[k][j]].min
#        end
#      end
#    end
    
    @log.print "[edges]\n"
    for i in 0...(@n_vertex + 1) do
      @log.print @edges[i].join(" ") + "\n"
    end
    @log.print "\n"
  end
  
  def read_t_max
    @t_max = gets.to_i
    @t_last = (@t_max.to_f * 0.95).to_i
    
    @log.print "[t_max] #{@t_max} [t_last] #{@t_last}\n\n"
  end
  
  def log_status
    @log.print "[t=] #{@time}\n"
    @log.print "curr_v=#{@curr_v} next_v=#{@next_v}\n"
    @log.print "way_len=#{@way_len} distance=#{@distance}\n"
  end
  
  def read_new_order
    n_new = gets
    if n_new.nil?
      @log.print "Panic! Invalid n_new!\n"
      return false
    else
      n_new = n_new.to_i
    end
    for i in 0...n_new do
      new_id, dst = gets.split.map(&:to_i)
      if @order_list[new_id].nil?
        @order_list[new_id] = [dst, @time, -1]
        @depot_order.push(@order_list[new_id])
        @log.print "[new order] new_id=#{new_id} dst=#{dst}\n"
      else
        @log.print "Panic! Invalid new_id!\n"
        return false
      end
    end
    return true
  end
  
  def simulate_depot
    return if @curr_v != 1 || @distance != 0
    
    @log.print "At depot\n"
    @load.concat(@depot_order)
    @depot_order = []
    
    @log.print "depot_order.size=#{@depot_order.size} load.size=#{@load.size}\n"
  end
  
  def simulate_destination
    return if @curr_v == 1 || @distance != 0
    
    @log.print "At destinations\n"
    @load.each_with_index do |order, id|
      next if order.nil?
      
      dst, ordered_time, delivered_time = order
      if dst == @curr_v && delivered_time < 0
        @log.print "delivered!\n"
        delivered_time = @time
        order[2] = delivered_time
        @point += @t_max ** 2 - (delivered_time - ordered_time) ** 2
        @log.print "point=#{@point}\n"
      end
    end
    @load.delete_if do |order|
      order[0] == @curr_v
    end
    
#    @load.each_with_index do |order, id|
#      next if order.nil?
#      
#      @log.print "load[#{id}]=[#{order[0]} #{order[1]} #{order[2]}]\n"
#    end
  end
  
  def simulate_move(command)
    return true if command == -1
    
    @log.print "Effective move\n"
    if @distance == 0
      @next_v = command
      @way_len = @edges[@curr_v][@next_v]
    else
      if command != @next_v && command != @curr_v
        @log.print "Panic! Invalid target_v!\n"
        return false
      end
    end
    @distance += 1
    if @distance == @way_len
      @curr_v = @next_v
      @next_v = -1
      @distance = 0
    end
    
    @log.print "[curr_v] #{@curr_v} [next_v] #{@next_v} [way_len] #{@way_len} [distance] #{@distance}\n\n"
    return true
  end
  
  def simulate_time
    @time += 1
    return (@time < @t_max)
  end
  
  def get_graph_info
    return [@n_vertex, @n_edge, @edges]
  end
  
  def get_time_info
    return [@time, @t_max, @t_last]
  end
  
  def get_current_position
    return [@curr_v, @next_v, @way_len, @distance]
  end
  
  def terminate
    @log.print "\n[total point=] #{@point}\n"
    @log.close
  end
end

class Strategy
  #
end

sim = Simulation.new
sim.read_graph
sim.read_t_max

visited = {}
ForwardMode = 0
BackwardMode = 1
mode = ForwardMode

n_vertex, n_edge, edges = sim.get_graph_info

while true do
  sim.log_status
  break if !sim.read_new_order
  sim.simulate_depot
  sim.simulate_destination
  
  t, t_max, t_last = sim.get_time_info
  break if t >= t_max
  
  curr_v, next_v, way_len, distance = sim.get_current_position
  if t < (t_max * 5 / 7)
    command = -1
  else
    if distance == 0
      visited[curr_v] = true
      command = -1
      way_len = -1
      for i in 0...n_vertex do
        ii = rand(n_vertex)
        if edges[curr_v][ii] > 0 && !visited.include?(ii)
          command = ii
          way_len = edges[curr_v][ii]
          break
        end
      end
      if command == -1
        for i in 0...n_vertex do
          ii = rand(n_vertex)
          if edges[curr_v][ii] > 0
            command = ii
            way_len = edges[curr_v][ii]
            break
          end
        end
      end
    end
  end
  puts command
  
  break if !sim.simulate_move(command)
  break if !sim.simulate_time
end

sim.simulate_depot
sim.simulate_destination
sim.terminate


Measured memory_bytes: 6140