INF = 1000000000

class Dijkstra
  def initialize(n, edges, start)
    d = Array.new(n + 1, INF)
    used = Array.new(n + 1, false)
    prev = Array.new(n + 1, -1)
    d[start] = 0
    
    while true do
      v = -1
      for u in 1...(n + 1) do
        v = u if !used[u] && (v == -1 || d[u] < d[v])
      end
      
      break if v == -1
      used[v] = true
      
      for u in 1...(n + 1) do
        if d[u] > d[v] + edges[v][u]
          d[u] = d[v] + edges[v][u]
          prev[u] = v
        end
      end
    end
    
    @paths = []
    for i in 1...(n + 1) do
      path = []
      t = i
      while t != -1 do
        path.unshift(t)
        t = prev[t]
      end
      @paths[i] = path
    end
  end
end

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
  attr_reader :log
  
  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), INF) }
    @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
    
    @dij = Dijkstra.new(@n_vertex, @edges, 1)
    # 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 command!\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

sim = Simulation.new
sim.read_graph
sim.read_t_max

visited = {}
path = []
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 < 100
    command = -1
  elsif distance == 0
    if curr_v == 1
      sim.log.print "Change to Forward\n"
      mode = ForwardMode
      visited = {}
      path = []
    end
    case mode
    when ForwardMode
      if path.length >= 100
        sim.log.print "Change to Backward\n"
        mode = BackwardMode
        command = path.pop
      else
        sim.log.print "Forward\n"
        visited[curr_v] = true
        path.push(curr_v)
        command = -1
        for i in 0...n_vertex do
          ii = rand(n_vertex)
          if edges[curr_v][ii] < INF && !visited.include?(ii)
            command = ii
            break
          end
        end
        if command == -1
          target = rand(5)
          count = 0
          for i in 0...n_vertex do
            if edges[curr_v][i] < INF
              command = i
              count += 1
              break if count > target
            end
          end
        end
      end
    when BackwardMode
      sim.log.print "Backward\n"
      command = path.pop
    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: 7164