INF = 1000000000

class Logging
  def initialize
    @enabled = 0
    timestamp = Time.now.strftime("%m%d_%H%M%S") # ("%Y%m%d_%H%M%S")
    @file = File.open("logA_#{timestamp}.txt", "wb") if @enabled == 1
  end
  def close
    @file.close if @enabled == 1
  end
  def puts(str)
    @file.puts(str) if @enabled == 1
  end
  def print(str)
    @file.print(str) if @enabled == 1
  end
end
Log = Logging.new

class Dijkstra
  attr_reader :paths
  
  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 = Array.new(n + 1, nil)
    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 Simulation
  attr_reader :dij
  attr_reader :load
  
  def initialize
    @point = 0
    @time = 0
    @order_list = []
    @depot_order = []
    @load = []
    @curr_v = 1
    @next_v = -1
    @way_len = 0
    @distance = 0
  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) }
    for i in 0...@n_edge do
      u, v, d = gets.split.map(&:to_i)
      @edges[u][v] = d
      @edges[v][u] = d
    end
    
    @dij = []
    for i in 1...(@n_vertex + 1) do
      @dij[i] = Dijkstra.new(@n_vertex, @edges, i)
    end
    
    Log.puts "[edges]"
    for i in 0...(@n_vertex + 1) do
      Log.puts @edges[i].join(" ")
    end
    Log.puts ""
  end
  
  def read_t_max
    @t_max = gets.to_i
    @t_last = (@t_max.to_f * 0.95).to_i
    
    Log.puts "[t_max] #{@t_max} [t_last] #{@t_last}"
    Log.puts ""
  end
  
  def log_status
    Log.puts "[t=] #{@time}"
    Log.puts "curr_v=#{@curr_v} next_v=#{@next_v}"
    Log.puts "way_len=#{@way_len} distance=#{@distance}"
  end
  
  def read_new_order
    n_new = gets
    if n_new.nil?
      Log.puts "Panic! Invalid n_new!"
      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.puts "[new order] new_id=#{new_id} dst=#{dst}"
      else
        Log.puts "Panic! Invalid new_id!"
        return false
      end
    end
    return true
  end
  
  def simulate_depot
    return if @curr_v != 1 || @distance != 0
    
    Log.puts "At depot"
    @load.concat(@depot_order)
    @depot_order = []
    
    Log.puts "depot_order.size=#{@depot_order.size} load.size=#{@load.size}"
  end
  
  def simulate_destination
    return if @curr_v == 1 || @distance != 0
    
    Log.puts "At destinations"
    @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.puts "delivered!"
        delivered_time = @time
        order[2] = delivered_time
        @point += @t_max ** 2 - (delivered_time - ordered_time) ** 2
        Log.puts "point=#{@point}"
      end
    end
    @load.delete_if do |order|
      order[0] == @curr_v
    end
    
#    @load.each_with_index do |order, id|
#      next if order.nil?
#      
#      Log.puts "load[#{id}]=[#{order[0]} #{order[1]} #{order[2]}]"
#    end
  end
  
  def simulate_move(command)
    return true if command == -1
    
    Log.puts "Effective move"
    if @distance == 0
      @next_v = command
      @way_len = @edges[@curr_v][@next_v]
    else
      if command != @next_v && command != @curr_v
        Log.puts "Panic! Invalid command!"
        return false
      end
    end
    @distance += 1
    if @distance == @way_len
      @curr_v = @next_v
      @next_v = -1
      @distance = 0
    end
    
    Log.puts "[curr_v] #{@curr_v} [next_v] #{@next_v} [way_len] #{@way_len} [distance] #{@distance}"
    Log.puts ""
    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.puts "\n[total point=] #{@point}"
  end
end

sim = Simulation.new
sim.read_graph
sim.read_t_max

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
      if sim.load.empty?
        path = nil
        path_counter = -1
        command = -1
        Log.puts "Rest"
      else
        dst = sim.load[0][0]
        path = sim.dij[curr_v].paths[dst]
        path_counter = 1
        command = path[path_counter]
        Log.puts "Change to Forward"
      end
    else
      if sim.load.empty?
        path = sim.dij[curr_v].paths[1]
        path_counter = 1
        command = path[path_counter]
        Log.puts "Back to depot"
      elsif path_counter >= path.length - 1
        dst = sim.load[0][0]
        path = sim.dij[curr_v].paths[dst]
        path_counter = 1
        command = path[path_counter]
        Log.puts "Found next dst"
      else
        path_counter += 1
        command = path[path_counter]
        Log.puts "Go to next vertex"
      end
    end
  end
  puts command
  
  break if !sim.simulate_move(command)
  break if !sim.simulate_time
end

sim.log_status
sim.simulate_depot
sim.simulate_destination
sim.terminate

Log.close


Measured memory_bytes: 49296