#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
const int inf = 1e9;

struct transfer{
    int from, to, direct_to, time;
    string name;
    transfer(int from, int to, int direct_to, int time, string name):
        from(from), to(to), direct_to(direct_to), time(time), name(name){}
    transfer(){}
    bool operator <(const transfer &a) const{
        return (time!=a.time)? time<a.time: direct_to<a.direct_to;
    }
};

int main(){
    bool is_first_dataset = true;
    while(1){
        int n,m;
        cin >> n >> m;
        if(n == 0) break;
        if(is_first_dataset){
            is_first_dataset = false;
        }else{
            cout << endl;
        }

        vector<vector<int>> dist_0(n, vector<int>(n, inf));
        for(int i=0; i<n; i++){
            dist_0[i][i] = 0;
        }
        for(int i=0; i<m; i++){
            int a,b,c;
            cin >> a >> b >> c;
            a--; b--;
            dist_0[a][b] = dist_0[b][a] = c;
        }
        auto dist = dist_0;
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
        vector<vector<int>> direct(n, vector<int>(n));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i == j){
                    direct[i][j] = i;
                    continue;
                }
                for(int k=0; k<n; k++){
                    if(k == i) continue;
                    if(dist_0[i][k] +dist[k][j] == dist[i][j]){
                        direct[i][j] = k;
                        break;
                    }
                }
            }
        }

        int q;
        cin >> q;
        vector<vector<transfer>> tr(n);
        priority_queue<int> event;
        for(int i=0; i<q; i++){
            int from,to,time;
            string name;
            cin >> from >> to >> time >> name;
            from--; to--;
            tr[from].emplace_back(from, to, direct[from][to], time, name);
            event.push(-time);
        }

        for(int i=0; i<n; i++){
            sort(tr[i].begin(), tr[i].end());
        }
        vector<int> rettime(n, 0);
        event.push(0);

        vector<pair<int,string>> ans;
        while(!event.empty()){
            int t = event.top();
            while(!event.empty() and event.top() == t){
                event.pop();
            }
            t = -t;
            for(int i=0; i<n; i++){
                if(t < rettime[i]) continue;
                if(tr[i].empty() or tr[i][0].time > t) continue;
                int dto = tr[i][0].direct_to;
                rettime[i] = t +2*dist[i][dto];
                event.push(-rettime[i]);
                event.push(-(t +dist[i][dto]));
                for(int j=(int)tr[i].size()-1; j>=0; j--){
                    if(tr[i][j].direct_to == dto and t >= tr[i][j].time){
                        if(tr[i][j].to == tr[i][j].direct_to){
                            ans.emplace_back(t +dist[i][dto], tr[i][j].name);
                        }else{
                            int to = tr[i][j].to;
                            tr[dto].emplace_back(dto, to, direct[dto][to], t+dist[i][dto], tr[i][j].name);
                        }
                        tr[i].erase(tr[i].begin() +j);
                    }                    
                }
                sort(tr[dto].begin(), tr[dto].end());
            }
        }
        sort(ans.begin(), ans.end());
        for(auto p: ans){
            cout << p.second << " " << p.first << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3344