import java.util.*

fun setRoute(officeCount:Int, routeInfo:Array<Triple<Int, Int, Int>>):Array<PostOffice> {
    val routes = Array(officeCount){Array(officeCount){
        Route(Int.MAX_VALUE)
    }}
    val office = Array(officeCount){PostOffice(it, routes[it])}
    routeInfo.forEach {(from, to, distance) ->
        routes[from - 1][to - 1] = Route(distance, office[to - 1])
        routes[to - 1][from - 1] = Route(distance, office[from - 1])
    }
    for (mid in 0 until officeCount) for (from in 0 until officeCount) for (to in 0 until officeCount){
        if (routes[from][mid].minCost < routes[from][to].minCost - routes[mid][to].minCost){
            routes[from][to] = Route(routes[from][mid].minCost + routes[mid][to].minCost, routes[from][mid].next)
            routes[to][from] = Route(routes[from][mid].minCost + routes[mid][to].minCost, routes[to][mid].next)
        }else if (routes[from][mid].minCost == routes[from][to].minCost - routes[mid][to].minCost){
            if (routes[from][to].next.id > routes[from][mid].next.id)
                routes[from][to].next = routes[from][mid].next
            if (routes[to][from].next.id > routes[to][mid].next.id)
                routes[to][from].next = routes[to][mid].next
        }
    }
    return office
}
fun main(args:Array<String>):Unit{
    var isNotFirst = false
    while(true){
        val (n, m) = readLine()!!.split(' ').map(String::toInt)
        if (n == 0 && m == 0) return
        val offices = setRoute(n, Array(m){
            val (f, t, d) = readLine()!!.split(' ').map(String::toInt)
            Triple(f, t, d)
        })
        val civilian:Civilian = Civilian()
        repeat(readLine()!!.toInt()){
            val arg = readLine()!!.split(' ')
            val (from, to, time) = arg.take(3).map(String::toInt)
            civilian.addPostSchedule(time, Mail(offices[to - 1], arg.last()), offices[from - 1])
        }
        if (isNotFirst) println()
        isNotFirst = true
        loopEvent(offices.map{it.officer} + civilian)
    }
}
typealias Mails = Collection<Mail>
interface Person{
    val nextSchedule:Event
}
class Officer(private val mOffice: PostOffice):Person{
    val id:Int = mOffice.id
    override var nextSchedule: Event = Event.NoEvent
        private set
    private var currentRelationalPosition:Int = 0
    fun addJobToReturn(currentTime:Int):Unit {
        nextSchedule = Event.SomeEvent.ReturnToOffice(currentTime + currentRelationalPosition, this)
        currentRelationalPosition = 0
    }
    fun findNewJob(currentTime:Int):Unit {
        nextSchedule = Event.NoEvent
        mOffice.returnOfficer(currentTime)
    }
    fun addJobToDeliverMails(currentTime:Int, distance:Int, mails: Mails, deliverAt:PostOffice):Unit {
        nextSchedule = Event.SomeEvent.DeliverMails(currentTime + distance, this, mails, deliverAt)
        currentRelationalPosition = distance
    }
}
class Civilian:Person{
    private val mSchedules:Deque<Event.SomeEvent.PostMail> = LinkedList()
    override val nextSchedule: Event
        get() = mSchedules.firstOrNull() ?: Event.NoEvent
    fun addPostSchedule(time:Int, mail:Mail, postAt:PostOffice):Unit {
        mSchedules.addLast(Event.SomeEvent.PostMail(time, mail, postAt, this))
    }
    fun receivedMail():Unit {
        mSchedules.removeFirst()
    }
}
class MailBox(val id:Int){
    var timeStamp:Int = Int.MAX_VALUE
        private set
    private val mMails:Stack<Mail> = Stack()
    val mails:Mails
        get() = mMails
    fun clear():Unit {
        timeStamp = Int.MAX_VALUE
        mMails.clear()
    }
    fun addMail(currentTime:Int, mail:Mail):Unit {
        if (timeStamp > currentTime){
            timeStamp = currentTime
        }
        mMails.push(mail)
    }
    fun isEmpty():Boolean = mMails.isEmpty()
}
class PostOffice(val id:Int, private val route:Array<Route>){
    val officer:Officer = Officer(this)
    private val mMail:Array<MailBox> = Array(route.size){MailBox(it)}
    fun postMail(currentTime:Int, mail:Mail):Unit {
        mMail[route[mail.destination.id].next.id].addMail(currentTime, mail)
        instructNewJob(currentTime)
    }
    fun addMails(currentTime:Int, mails:Mails):Unit {
        mails.forEach {
            mMail[route[it.destination.id].next.id].addMail(currentTime,it)
        }
        instructNewJob(currentTime)
    }
    fun returnOfficer(currentTime:Int):Unit {
        when(officer.nextSchedule){
            is Event.NoEvent -> {
                val mailBox = mMail.filterNot{it.isEmpty()}.minBy { it.timeStamp }
                when(mailBox){
                    null -> return
                    else -> {
                        officer.addJobToDeliverMails(currentTime, route[mailBox.id].minCost, mailBox.mails, route[mailBox.id].next)
                        mailBox.clear()
                    }
                }
            }
            else -> return
        }
    }
    private fun instructNewJob(currentTime:Int):Unit {
        when(officer.nextSchedule){
            is Event.NoEvent -> officer.addJobToReturn(currentTime)
            else -> return
        }
    }
}

class Route(val minCost:Int, private var mNext:PostOffice? = null){
    var next:PostOffice
        get() = mNext!!
        set(value){
            mNext = value
        }
}
class Mail(val destination:PostOffice, val label:String)
sealed class Event {
    object NoEvent : Event()
    sealed class SomeEvent(val time: Int) : Event(), Comparable<SomeEvent> {
        protected abstract fun compareToWithType(other: SomeEvent): Int
        override fun compareTo(other: SomeEvent): Int {
            return when (time) {
                other.time -> compareToWithType(other)
                else -> time.compareTo(other.time)
            }
        }

        class PostMail(time: Int, val mail: Mail, val office: PostOffice, val poster: Civilian) : SomeEvent(time) {
            override fun compareToWithType(other: SomeEvent): Int {
                return when (other) {
                    is PostMail -> 0
                    else -> -1
                }
            }
        }

        class DeliverMails(time: Int, val officer: Officer, mails: Mails, val next: PostOffice) : SomeEvent(time) {
            override fun compareToWithType(other: SomeEvent): Int {
                return when (other) {
                    is PostMail -> 1
                    else -> 0
                }
            }

            val mailsToDestination: Mails = mails.filter { it.destination == next }
            val mailsToRelay: Mails = mails.filterNot { it.destination == next }
        }

        class ReturnToOffice(time: Int, val officer: Officer) : SomeEvent(time) {
            override fun compareToWithType(other: SomeEvent): Int {
                return when (other) {
                    is ReturnToOffice -> 0
                    else -> 1
                }
            }
        }
    }
}
fun loopEvent(persons:Collection<Person>):Unit {
    val result: Stack<Pair<String, Int>> = Stack()
    loop@while (true){
        val event = persons.mapNotNull { it.nextSchedule as? Event.SomeEvent }.min()
        when (event) {
            is Event.SomeEvent.PostMail -> {
                //println("time = ${event.time}, post = ${event.mail.label}, at = ${event.office.id}")
                event.office.postMail(event.time, event.mail)
                event.poster.receivedMail()
            }
            is Event.SomeEvent.DeliverMails -> {
                //println("time = ${event.time}, officer = ${event.officer.id}, deliver = ${event.mailsToDestination.joinToString(",") { it.label }}, ${event.mailsToRelay.joinToString(",") { it.label }}, office = ${event.next.id}")
                result.addAll(event.mailsToDestination.map { Pair(it.label, event.time) })
                event.next.addMails(event.time, event.mailsToRelay)
                event.officer.addJobToReturn(event.time)
            }
            is Event.SomeEvent.ReturnToOffice -> {
                //println("time = ${event.time}, officer = ${event.officer.id} return")
                event.officer.findNewJob(event.time)
            }
            null -> break@loop
        }
    }
    println(
            result.sortedWith(compareBy(Pair<String, Int>::second, Pair<String,Int>::first)).joinToString("\n") { "${it.first} ${it.second}" }
    )
}


Measured memory_bytes: 79164