#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>

using namespace std;
const int INF=1000000000;

struct edge{
    int to;
    int cost;
};

struct Letter{
    int nxtTo;
    int goal;
    int start;
    int id;
    int arriveTime;
    bool operator<(const Letter &lt)const{
        if(arriveTime>lt.arriveTime)return true;
        else if(arriveTime<lt.arriveTime)return false;
        return nxtTo>lt.nxtTo;
    }
};

struct Event{
    // 0:,1:úÔ,2:èÌÇÁ
    int kind;
    int time;
    int node;
    int prvNode;
    vector<Letter> lts;
    bool operator<(const Event &e)const{
        if(time>e.time)return true;
        else if(time<e.time)return false;
        return kind>e.kind;
    }
};

int d[33][33];
// cur,to
int nxt[33][33];
string letterNames[1001];
vector<edge>G[101];
int N,M,L;
// Çõª¶Ý·é©Ç¤©
bool isExist[1001];
// eXÖÇÉÂ¢ÄA»ê¼êÌèª·ÅÉçê½©
bool isArrivalLet[1001][1001];
// eXÖÇ²ÆÉAèðÔÉÇ
priority_queue<Letter> postLets[1001];
// eXÖÇ²ÆÉAèð Äæ²ÆÉÇ
vector<Letter> postByNxtTo[101][101];

void warshall_floyd(int V){
    for(int i=0;i<V;i++)
        for(int j=0;j<V;j++)
            for(int k=0;k<V;k++)
                d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
}
void calcNxtPlace(int V){
    for(int i=0;i<33;i++)for(int j=0;j<33;j++)nxt[i][j]=INF;
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            if(i!=j){
                int nxtNum=INF;
                for(int k=0;k<G[i].size();k++){
                    edge &e=G[i][k];
                    if(e.cost+d[e.to][j]==d[i][j])nxtNum=min(nxtNum,e.to);
                }
                nxt[i][j]=nxtNum;
            }
        }
    }
}
int main(){
    bool fst=true;
    while(cin>>N>>M&&(N|M)){
        if(fst)fst=false;
        else cout<<endl;
        memset(isArrivalLet,0,sizeof(isArrivalLet));
        for(int i=0;i<N;i++)G[i].clear();
        for(int i=0;i<1001;i++)isExist[i]=true;
        for(int i=0;i<101;i++)for(int j=0;j<101;j++)postByNxtTo[i][j].clear();
        for(int i=0;i<N;i++)while(postLets[i].size())postLets[i].pop();
        for(int i=0;i<N;i++)for(int j=0;j<N;j++){
            if(i==j)d[i][j]=0;
            else d[i][j]=INF;
        }
        for(int i=0;i<M;i++){
            int a,b,c;
            edge e;
            cin>>a>>b>>e.cost;
            a--;b--;
            e.to=b;
            G[a].push_back(e);
            e.to=a;
            G[b].push_back(e);
            d[a][b]=d[b][a]=e.cost;
        }
        warshall_floyd(N);
        calcNxtPlace(N);
        cin>>L;
        priority_queue<Event> pq;
        for(int i=0;i<L;i++){
            Letter lt;
            cin>>lt.start>>lt.goal>>lt.arriveTime;
            lt.start--;lt.goal--;
            cin>>letterNames[i];
            lt.id=i;
            lt.nxtTo=(nxt[lt.start][lt.goal]);
            // èÇÁCxg
            Event ev;
            ev.prvNode=lt.start;
            ev.node=lt.start;
            ev.kind=1;
            ev.time=lt.arriveTime;
            ev.lts.push_back(lt);
            pq.push(ev);
        }
        vector<pair<int,string> > res;
        // CxgðÔÉ
        while(pq.size()){
            Event e=pq.top();pq.pop();
            // 
            if(e.kind==0){
                // èðXÖÇÉÇÁ
                for(int i=0;i<e.lts.size();i++){
                    // goal
                    if(e.lts[i].goal==e.node)
                        res.push_back(make_pair(e.time,letterNames[e.lts[i].id]));
                    else{
                        //  ÄæðÌêÉÏXµÄ¨­
                        e.lts[i].nxtTo=nxt[e.node][e.lts[i].goal];
                        e.lts[i].arriveTime=e.time;
                        postLets[e.node].push(e.lts[i]);
                        postByNxtTo[e.node][e.lts[i].nxtTo].push_back(e.lts[i]);
                    }
                }
                // AÒCxgðÇÁ
                {
                    Event ev;
                    ev.node=e.prvNode;
                    ev.kind=2;
                    ev.prvNode=e.node;
                    // ÌCxgÔðo^
                    ev.time=e.time+d[e.node][e.prvNode];
                    pq.push(ev);
                }
                // Ì]æÖéCxgðÇÁ
                {
                    // wõª¢éÈçÎAo­CxgðÇÁ
                    if(isExist[e.node]){
                        isExist[e.node]=false;
                        Event ev;
                        ev.kind=3;
                        ev.time=e.time;
                        ev.node=e.node;
                        pq.push(ev);
                    }
                }
            }
            // ÇÁ
            else if(e.kind==1){
                // èðXÖÇÉÇÁ
                postLets[e.node].push(e.lts[0]);
                // èðXÖÇÉ Äæ²ÆÉª¯ÄÇÁ
                postByNxtTo[e.node][e.lts[0].nxtTo].push_back(e.lts[0]);
                // wõª¢éÈçÎAo­CxgðÇÁ
                if(isExist[e.node]){
                    isExist[e.node]=false;
                    Event ev;
                    ev.kind=3;
                    ev.time=e.time;
                    ev.node=e.node;
                    pq.push(ev);
                }
            }
            // AÒ
            else if(e.kind==2){
                isExist[e.node]=true;
                // wõª¢éÈçÎAo­CxgðÇÁ
                if(isExist[e.node]){
                    isExist[e.node]=false;
                    Event ev;
                    ev.kind=3;
                    ev.time=e.time;
                    ev.node=e.node;
                    pq.push(ev);
                }
            }
            // o­
            else if(e.kind==3){
                // ¡ éèÌÅAàÁÆàÔªÍâ¢àÌðé
                // ½¾µAÌ Ä³«ª¨È¶àÌÍAÜÆßÄé
                // ¡±ÌêÉèª¶ÝµÈ¢
                Letter lt;
                bool ok=true;
                while(1){
                    if(postLets[e.node].empty()){
                        ok=false;
                        break;
                    }
                    lt=postLets[e.node].top();postLets[e.node].pop();
                    // ·ÅÉçêÄ¢é
                    if(isArrivalLet[e.node][lt.id])continue;
                    else break;
                }
                if(!ok){
                    isExist[e.node]=true;
                    continue;
                }
                Event ev;
                // éèðZbg
                ev.lts=postByNxtTo[e.node][lt.nxtTo];
                // Á½ÌÅgðNA
                for(int i=0;i<ev.lts.size();i++)isArrivalLet[e.node][ev.lts[i].id]=true;
                postByNxtTo[e.node][lt.nxtTo].clear();
                ev.kind=0;
                ev.node=lt.nxtTo;
                ev.prvNode=e.node;
                ev.time=e.time+d[e.node][lt.nxtTo];
                pq.push(ev);
            }
        }
        sort(res.begin(),res.end());
        for(int i=0;i<res.size();i++)cout<<res[i].second<<" "<<res[i].first<<endl;
    }
    return 0;
}

Measured memory_bytes: 0