class Heap
	require 'forwardable'
	extend Forwardable

	def initialize
		@array = []
		@index = {}
	end

	def add(obj, key)
		@array << [obj, key]
		@index[obj] = @array.size - 1
		lift_up(@array.size - 1)
	end

	def swap(i, j)
		u = @array[i]
		v = @array[j]
		@index[u[0]], @index[v[0]] = j, i
		@array[i], @array[j] = v, u
	end

	def lift_up(i)
		return if i == 0
		j = (i - 1) / 2
		if (@array[i][1] <=> @array[j][1]) < 0
			swap(i, j)
			lift_up(j)
		end
	end

	def del_min
		raise "heap is empty!" if empty?
		min = @array[0]
		if size > 1
			swap(0, @array.size-1)
			@array.pop
			lift_down(0)
		else
			@array.pop
		end
		@index.delete(min[0])
		min
	end

	def inc_key(obj, diff)
		i = @index[obj]
		@array[i][1] += diff
		lift_down(i)
	end

	def dec_key(obj, diff)
		i = @index[obj]
		@array[i][1] -= diff
		lift_up(i)
	end

	def update_key(obj, new_key)
		i = @index[obj]
		return unless i
		return if (new_key <=> @array[i][1]) >= 0
		@array[i][1] = new_key
		lift_up(i)
	end

	def min_obj
		@array[0][0]
	end

	def min_key
		@array[0][1]
	end

	def lift_down(i)
		j = 2 * i + 1
		k = j + 1
		if k >= size
			return if j >= size
			if (@array[i][1] <=> @array[j][1]) > 0
				swap(i, j)
				lift_down(j)
			end
		else
			l = ((@array[j][1] <=> @array[k][1]) < 0 ? j : k)
			if (@array[i][1] <=> @array[l][1]) > 0
				swap(i, l)
				lift_down(l)
			end
		end
	end

	def_delegators :@array, :empty?, :size
end

def warshall_floyd(dist_matrix)
	dist = dist_matrix
	n = dist.size
	raise "dist_matrix is not square" if dist.any?{|row| row.size != n}

	next_dist = (1..n).map{ Array.new(n) }
	(0..n-1).each{|k|
		dist_k = dist[k]
		(0..n-1).each{|i|
			dist_i = dist[i]
			next_dist_i = next_dist[i]
			(0..n-1).each{|j|
				x = dist_i[j]
				y = dist_i[k] + dist_k[j]
				next_dist_i[j] = (x < y ? x : y)
			}
		}
		dist = next_dist
	}
	dist
end

ans = []
loop do
    n, m = gets.split.map(&:to_i)
    break if n == 0
    ans << []

    d_mat = (0..n).map {(0..n).map {Float::INFINITY}}
    (1..n).map {|i| d_mat[i][i] = 0}
    m.times do
        i, j, d = gets.split.map(&:to_i)
        d_mat[i][j] = d_mat[j][i] = d
    end
    dist = warshall_floyd(d_mat)

    routing = (0..n).map {[nil] * (n+1)}
    (1..n).each do |u|
        (1..n).each do |v|
            if u == v
                routing[u][v] = u
            else
                routing[u][v] = (1..n).min_by do |w|
                    if w == u || d_mat[u][w] == Float::INFINITY
                        [Float::INFINITY, -1]
                    else
                        [d_mat[u][w] + dist[w][v], w]
                    end
                end
            end
        end
    end

    event_queue = Heap.new
    at_home = Hash.new(true)

    hash = (0..n).map { {} }
    queue = (0..n).map { Heap.new }

    l = gets.to_i
    l.times do
        u, v, t, name = gets.chomp.split
        event_queue.add([:new, name, u.to_i, v.to_i], t.to_i)
    end

    until event_queue.empty?
        t0 = event_queue.min_key
        while ! event_queue.empty? && event_queue.min_key == t0
            event, _ = event_queue.del_min
            case event[0]
            when :new
                _, name, from, orig_to = event
                to = routing[from][orig_to]
                if hash[from][to]
                    hash[from][to] << [orig_to, name]
                else
                    queue[from].add(to, [t0, to])
                    hash[from][to] = [[orig_to, name]]
                end
            when :return
                _, u = event
                at_home[u] = true
            when :arrival
                _, name, to, orig_to = event
                if to == orig_to
                    ans[-1] << [name, t0]
                else
                    next_to = routing[to][orig_to]
                    if hash[to][next_to]
                        hash[to][next_to] << [orig_to, name]
                    else
                        queue[to].add(next_to, [t0, next_to])
                        hash[to][next_to] = [[orig_to, name]]
                    end
                end
            end
        end

        (1..n).map do |from|
            next if ! at_home[from]
            next if queue[from].empty?
            to, _ = queue[from].del_min
            hash[from][to].each do |orig_to, name|
                event = [:arrival, name, to, orig_to]
                t = t0 + d_mat[from][to]
                event_queue.add(event, t)
            end
            hash[from].delete(to)

            at_home[from] = false
            event = [:return, from]
            t = t0 + 2 * d_mat[from][to]
            event_queue.add(event, t)
        end
    end
end

puts ans.map {|a| a.sort_by {|name, t| [t, name]}.map{|name, t| "#{name} #{t}"}.join("\n")}.join("\n\n")

Measured memory_bytes: 10288