#include <iostream>
#include <list>
#include <string>
#include <set>
using namespace std;

#define BUF 100
int N, M, L;
pair<int, int> D[BUF][BUF]; // グラフ
// firstは所要時間、secondは次の郵便局
int PTime[BUF];  // 郵便局が次に稼動できる時刻

void warshall(){
  for(int k=1; k<=N; k++){
    for(int i=1; i<=N; i++) if(i != k){
      for(int j=1; j<=N; j++) if(j != k){
        if(D[i][k].first >= 0 && D[k][j].first >= 0){
          if(D[i][j].first < 0 || 
             D[i][j].first > D[i][k].first + D[k][j].first ||
             (D[i][j].first == D[i][k].first + D[k][j].first &&
              D[i][j].second > D[i][k].second)){
            D[i][j] = make_pair(D[i][k].first + D[k][j].first,
                                D[i][k].second);
          }
        }
      }
    }
  }
}


struct mail {
  string label;    // 郵便物のラベル
  int to;          // 目的地
  int pos;         // 現在地
  int time;        // 次に移動可能となる時間
  int atime;       // 現在地への到着時刻
  
  mail(string l, int t, int p, int tm, int a)
   : label(l), to(t), pos(p), time(tm), atime(a) {
  }
  
  int next() const {
    return D[pos][to].second;
  }

  mail wait(int tm) const{
    return mail(label, to, pos, tm, atime);
  }

  mail move() const{
    int d = D[pos][next()].first;
    int n = next();
    if(n == to){
      return mail(label, -1, -1, time + d, time + d);
    }
    return mail(label, to, n, time + d, time + d);
  }
};

bool operator < (const mail &m1, const mail &m2){
  // 時刻順にシミュレート
  if(m1.time != m2.time){ return (m1.time < m2.time); }
  // 先に到着したもの優先
  if(m1.atime != m2.atime){ return (m1.atime < m2.atime); }
  // 転送先の番号の若いもの優先
  if(m1.next() != m2.next()){ return (m1.next() < m2.next()); }
  // 出力はラベル順
  if(m1.label != m2.label){ return (m1.label < m2.label); }
  // 一応、適当に順位設定
  if(m1.pos != m2.pos){ return (m1.pos < m2.pos); }
  return false;
}

void solve(set<mail> mails){
  while(!mails.empty()){
    /*
    for(set<mail>::iterator p = mails.begin(); p != mails.end(); ++p){
      cout << "#" << p->label << " " << p->pos << " > " << p->next() << " " << p->time << endl;
    }
    cout << endl;
    */
    
    mail m = *(mails.begin());
    mails.erase(mails.begin());
    // cout << m.label << " " << m.pos << " " << m.time << endl;
    if(m.to < 0){
      cout << m.label << " " << m.atime <<endl;
    }else if(PTime[m.pos] <= m.time){
      mails.insert(m.move());
      bool change = true;
      while(change){
        change = false;
        for(set<mail>::iterator p = mails.begin(); p != mails.end(); ++p){
          // cout << " #" << p->label << endl;
          if(p->pos == m.pos && p->time == m.time && p->next() == m.next()){
            mails.insert(p->move());
            mails.erase(p);
            change = true;
          }
        }
      }
      PTime[m.pos] = m.time + D[m.pos][m.next()].first * 2;
    }else{
      mails.insert(m.wait(PTime[m.pos]));
    }
  }
}

int main(){
  for(int iii=0; cin >> N >> M; iii++){
    if(N == 0 && M == 0){ break; }
    if(iii > 0){ cout << endl; }
    for(int i=0; i< BUF; i++){
      for(int j=0; j< BUF; j++){
        if(i == j){
          D[i][j] = make_pair(0, j);
        }else{
          D[i][j] = make_pair(-1, -1);
        }
      }
      PTime[i] = 0;
    }
    for(int i=0; i<M; i++){
      int f, t, d;
      cin >> f >> t >> d;
      D[f][t] = make_pair(d,t);
      D[t][f] = make_pair(d,f);
    }
    warshall();
    /*
    for(int i=1; i<=N; i++){
      for(int j=1; j<=N; j++){
        cout << "(" << D[i][j].first << "," << D[i][j].second << ")";
      }
      cout << endl;
    }
    */
    set<mail> mails;
    cin >> L;
    for(int i=0; i<L; i++){
      int f, to, tm;
      string l;
      cin >> f >> to >> tm >> l;
      mails.insert(mail(l, to, f, tm, tm));
    }
    solve(mails);
  }
}