#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 50

bool firstcase = true;

struct DATA{
  ll t;
  int id;
  int now;
  int next;
  int goal;

  const bool operator<(const DATA &B) const{
    if(t != B.t) return t > B.t;
    if(next != B.next) return next > B.next;
    return false;
  }

  DATA(ll t, int id, int now, int next, int goal):
    t(t), id(id), now(now), next(next), goal(goal){}
};

int dist[40][40];
int connect[40][40];
int n;

int getNext(int a, int b){
  if (a == b) return a;
  for(int i=0;i<n;i++){
    if(connect[a][i] && connect[a][i] == dist[a][i] && dist[a][i] + dist[i][b] == dist[a][b])
      return i;
  }

  assert(false);
  return -1;
}

bool solve(){
  int m, q;
  string text[1000];
  
  priority_queue<DATA> pq;

  scanf("%d%d", &n, &m);
  
  if(n == 0) return false;
  if(firstcase) firstcase = false;
  else puts("");
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      dist[i][j] = INF;
      connect[i][j] = false;
    }
    dist[i][i] = 0;
  }
  
  
  for(int i=0;i<m;i++){
    int a, b, c; 
    scanf("%d%d%d", &a, &b, &c);
    a--; b--;

    dist[a][b] = dist[b][a] = c;
    connect[a][b] = connect[b][a] = c;
  }

  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]);
  
  scanf("%d", &q);

  for(int i=0;i<q;i++){
    int a, b, t;
    char temp[60];
    scanf("%d%d%d%s", &a, &b, &t, temp);
    a--; b--;
    text[i] = temp;
    
    pq.push(DATA(t, i, a, getNext(a,b), b));
  }

  bool outside[40] = {};
  ll sent[40][40] = {};
  priority_queue<pair<ll,int> > que[40];
  queue<DATA> post[40][40];
  vector<pair<ll,string> > ans;

  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      sent[i][j] = -1;
  
  while(pq.size()){
    queue<int> work;
    ll t = pq.top().t;
    
    while(pq.size() && pq.top().t == t){
      auto p = pq.top(); pq.pop();
      if(p.id != -1){
        if(p.now == p.goal){
          ans.push_back({p.t, text[p.id]});
          continue;
        }
        
        post[p.now][p.next].push(p);
        que[p.now].push({-p.t, -p.next});
        // cerr << "[post] " << t << " : " << p.now << " -> " << p.next << " -> " << p.goal << endl;
      }else{
        assert(outside[p.now]);
        outside[p.now] = false;
        // cerr << "[back] " << t << " : " << p.now << endl;
      }

      work.push(p.now);
    }
    

    while(work.size()){
      int now = work.front(); work.pop();
      if(outside[now]) continue;
      
      while(que[now].size() && -que[now].top().first <= t){
        auto p = que[now].top(); que[now].pop();

        if(-p.first <= sent[now][-p.second]) continue;
        
        //cerr << now << " -> " << -p.second << endl;
        
        while(post[now][-p.second].size()){
          auto p2 = post[now][-p.second].front(); post[now][-p.second].pop();
          
          p2.t = t + dist[now][p2.next];
          p2.now = p2.next;
          p2.next = getNext(p2.next, p2.goal);
          pq.push(p2);
        }
        
        outside[now] = true;
        pq.push(DATA((ll)t + dist[now][-p.second]*2, -1, now, -1, -1));
        sent[now][-p.second] = t;
        break;
      }

    }
  }

  sort(ans.begin(), ans.end());

  assert(ans.size() == q);
  
  for(int i=0;i<q;i++){
    cout << ans[i].second << " " << ans[i].first << endl;
  }
  
  return true;
}


int main(){
  while(solve());
  
  return 0;
}



Measured memory_bytes: 4452