#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <utility>
#include <cassert>
#include <cstdio>

using namespace std;
const int INF = 1e9;

struct mail{
  int time, to, cur, next, id;
};

bool operator < (const mail &a, const mail &b){
  if(a.time != b.time) return a.time > b.time;
  if(a.next != b.next) return a.next > b.next;
  return a.cur > b.cur;
}

int main(){
  int n, m, c = 0;
  while(cin >> n >> m, n){
    if(c) printf("\n");
    else ++c;
    vector< vector<int> > D(n, vector<int>(n, INF)), E(n, vector<int>(n, 0));

    
    for(int i = 0; i < m; ++i){
      int u, v, d;
      cin >> u >> v >> d;
      --u;--v;
      D[u][v] = d;
      D[v][u] = d;
      E[u][v] = d;
      E[v][u] = d;
    }

    for(int i = 0; i < n; ++i) D[i][i] = 0;
    for(int k = 0; k < n; ++k){
      for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
          D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

        }
      }
    }

    vector< vector<int> > next(n, vector<int>(n, -1));
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        for(int k = 0; k < n; ++k){
          if(i == k || (D[i][k] + D[k][j] != D[i][j]) || (D[i][k] != E[i][k])) continue;
          next[i][j] = k;
          break;
        }
      }
    }

    int l;
    cin >> l;
    vector<string> name(l);
    priority_queue<mail> pque;
    
    for(int i = 0; i < l; ++i){
      int from, to, time;
      cin >> from >> to >> time >> name[i];
      pque.push((mail){time, to-1, from-1, next[from-1][to-1], i});
    }
    
    vector<int> T(n, -1);
    vector< vector<int> > U(n, vector<int>(n, -1));
    vector< pair<int, string> > A;
    
    while(!pque.empty()){
      mail x = pque.top();
      pque.pop();
      
      if(U[x.cur][x.next] < x.time){
        T[x.cur] = max(T[x.cur], x.time);
        U[x.cur][x.next] = T[x.cur];
        T[x.cur] = max(T[x.cur], U[x.cur][x.next] + 2*D[x.cur][x.next]);
      }
      x.time = U[x.cur][x.next] + D[x.cur][x.next];
      x.cur = x.next;
      x.next = next[x.cur][x.to];

      if(x.cur == x.to){
        A.push_back(make_pair(x.time, name[x.id]));
      }else{
        pque.push(x);
      }
    }
    
    sort(A.begin(), A.end());
    for(int i = 0; i < l; ++i){
      cout << A[i].second << " " << A[i].first << endl;
    }
  }
  return 0;
}

