#include <iostream>
#include <iomanip>
#include <list>
#include <set>
#include <vector>
#include <cassert>
#include <algorithm>
#include <utility>

//
// 1. まず、郵便局間の転送経路を求める。
// 2. 後はだるーいシミュレーションを書けばよい。
//

using namespace std;

const int NOT_CONNECTED = 1000000;  // ad-hoc.

struct Mail
{
  Mail(int time, int mail, const string& name) : time(time), mail(mail), name(name) {}
  
  int       time;        // いつ到着したか
  int       mail;        // とこにとどければよいか？
  string    name;        // お手紙のなまえ
};

inline bool operator<(const Mail& lhs, const Mail& rhs)
{
  if (lhs.time != rhs.time) { return lhs.time < rhs.time; }
  if (lhs.mail != rhs.mail) { return lhs.mail < rhs.mail; }
  return lhs.name < rhs.name;
}

void solve(const vector<vector<pair<int, int> > >& table, vector<list<Mail> >& mails)
{
  int n = mails.size();
  list<Mail> output;
  
  // mails に、メールがたまっているわけだが、mails は常にソートされているとしよう。
  // 一応イベント駆動ぽく、調べる時間を限定してみよう
  set<int> event_times; // event が起こる時刻
  for (vector<list<Mail> >::iterator it = mails.begin(); it != mails.end(); ++it) {
    for (list<Mail>::iterator that = it->begin(); that != it->end(); ++that) {
      event_times.insert(that->time);
    }
  }
  
  // おのおのの郵便局は、次のものを管理する必要がある。
  // 1. 次に作業を開始できる時間
  // 2. メール
  vector<int>  workable(n, 0); // 次に局員が動ける時刻

  while (!event_times.empty()) {
    int curtime = *event_times.begin();
    event_times.erase(event_times.begin());
    // cout << "+++++++ curtime: " << curtime << endl;
    
    for (int i = 0; i < n; ++i) {
      // 動ける時間より前、メールがない、次に届くメールがまだ付いてない -> あとまわし。
      if (curtime < workable[i] || mails[i].empty()) { continue; }
      if (mails[i].front().time > curtime) { continue; }
      
      int arrived_time = mails[i].front().time;
      
      // 2. 同じ所に持って行けるものを全部得て、持って行く。
      // まず、次に行くところを決める。
      
      int dest = table[i][mails[i].front().mail].second;
      int cost = table[i][mails[i].front().mail].first;
      for (list<Mail>::iterator it = mails[i].begin(); it != mails[i].end() && it->time == arrived_time; ++it) {
        if (table[i][it->mail].second < dest) {
          dest = table[i][it->mail].second;
          cost = table[i][it->mail].first;
        }
      }

      //    到着時間を event_times に記録し、メールも配達
      assert(dest != i);
      
      list<Mail>::iterator it = mails[i].begin();
      while (it != mails[i].end() && it->time <= curtime) {
        if (table[i][it->mail].second == dest) { 
          if (it->mail == dest) {
            // cout << "*** " << it->name << " " << (curtime + cost) << endl;
            output.push_back(Mail(curtime + cost, -1, it->name));
          } else {
            // cout << "--- " << curtime << ": " << it->name << ": " << i << " -> " << dest << ": " << (curtime + cost) << endl;
            Mail m(curtime + cost, it->mail, it->name);
            mails[dest].insert(lower_bound(mails[dest].begin(), mails[dest].end(), m), m);
            // mails[dest].push_back(m);
            event_times.insert(curtime + cost);
          }
          it = mails[i].erase(it);
        } else { // 対象じゃないので、無視
          ++it;
        }
      }
      
      // 3. 帰ってくる時間を workable に指定し、event_times にそれを記録
      workable[i] = curtime + cost * 2;
      event_times.insert(curtime + cost * 2);
    }
  }

  // 表示
  output.sort();
  for (list<Mail>::iterator it = output.begin(); it != output.end(); ++it) {
    cout << it->name << ' ' << it->time << endl;
  }
}


int main(void)
{
  int cnt = 0;
  int n, m; // n: 郵便局数, m: 転送経路数
  while (cin >> n >> m, n || m) {

    if (cnt++) { cout << endl; }
  
    // (first, second) = (距離, 次の経路)
    vector<vector<pair<int, int> > > table(n, vector<pair<int, int> >(n, make_pair(NOT_CONNECTED, 0)));
    vector<vector<pair<int, int> > > work_table(n, vector<pair<int, int> >(n, make_pair(NOT_CONNECTED, 0)));
    
    for (int i = 0; i < m; ++i) {
      int from, to, dist;
      cin >> from >> to >> dist;
      // note: 0-origin
      table[from - 1][to - 1] = make_pair(dist, to - 1);
      table[to - 1][from - 1] = make_pair(dist, from - 1);
      
      work_table[from - 1][to - 1] = table[from - 1][to - 1];
      work_table[to - 1][from - 1] = table[to - 1][from - 1];
    }

    // Floyd で、最短距離と距離と次の経路をつくる。
    for (int i = 0; i < n; ++i) { work_table[i][i] = make_pair(NOT_CONNECTED, i); }
    
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (work_table[i][j].first > work_table[i][k].first + work_table[k][j].first) {
            work_table[i][j].first  = work_table[i][k].first + work_table[k][j].first;
            work_table[i][j].second = work_table[i][k].second;
          } else if (work_table[i][j].first == work_table[i][k].first + work_table[k][j].first) {
            work_table[i][j].second = min(work_table[i][j].second, work_table[i][k].second);
          }
        }
      }
    }

    // work_table から、table にコピー
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j) {
          table[i][j].second  = work_table[i][j].second;
          table[i][j].first = table[i][table[i][j].second].first;
        } else {
          table[i][j].first = -1;  // ここを使うのは間違いなので、segv を起こさせる。
          table[i][j].second = NOT_CONNECTED;
        }
      }
    }
    
#if 0
    // ちょっとチェックでありますよ。
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        char buf[256];
        sprintf(buf, "(%d, %d)", work_table[i][j].first, work_table[i][j].second);
        cout << setw(10) << buf;
      }
      cout << endl;
    }

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        char buf[256];
        sprintf(buf, "(%d, %d)", table[i][j].first, table[i][j].second);
        cout << setw(10) << buf;
      }
      cout << endl;
    }
#endif

    // あと読み込んで、シミュレーション。
    vector<list<Mail> > mails(n);
    
    int l;
    cin >> l;
    for (int i = 0; i < l; ++i) {
      // note: 0-origin
      int from, to, time;
      string name;
      cin >> from >> to >> time >> name;
      mails[from - 1].push_back(Mail(time, to - 1, name));
    }

    for (int i = 0; i < n; ++i) { mails[i].sort(); }
    
    solve(table, mails);
  }
  
  return 0;
}