#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <stdarg.h>
using namespace std;

/*** Debug code **************************************************************/
static
int     debug_level      = 0;

static
void debug_print(const char *pat, ...)
{
  static char buffer[4096];
  va_list ap;
  va_start(ap, pat);
  vsnprintf(buffer, sizeof(buffer) - 1, pat, ap);
  va_end(ap);
  cout << buffer;
}
#define ifdebug(lev) if( debug_level >= (lev) )
#define debug(lev, pat, ...) ifdebug(lev) debug_print(pat, __VA_ARGS__)

/*** Constant Definitions ****************************************************/
#define NOT_CONN   10000000
#define ON_THE_WAY (-1)

/*** Data Structures *********************************************************/

// Parcel Description
struct parcel {
  int    stime;
  string id;
  int    src, dest;

  parcel(int stime, string id, int src, int dest)
       : stime(stime), id(id), src(src), dest(dest)
    {}
};

// Simulation Event Structure
struct event {
  int          tm;
  enum event_type_t {
    postman_t = 0,
    parcel_t  = 1,
  }            type;
  int          place;

  int          id;    // parcel id or postoffice id (postman's home)

  event(int tm, event_type_t type, int id, int place)
       : tm(tm), type(type), id(id), place(place)
    {}
};

bool operator < (const event& a, const event& b)
{
  // time ASC, place ASC, type DESC
  // revert order for priority queue
  if(a.tm != b.tm)       return a.tm > b.tm;
  if(a.place != b.place) return a.place > b.place;
  if(a.type != b.type)   return a.type < b.type;
  return false;
}

/*** Solver Routine **********************************************************/

void solve(vector<vector<int> >& dist, const vector<parcel>& parcels)
{
  const int N = dist.size();
  vector<vector<int> >           next(N, vector<int>(N, -1));
  vector<pair<int, string> >     result;
  priority_queue<event>          Q;
  vector<list<pair<int, int> > > dispatch_queue(N);
  vector<int>                    postman_pos(N);
  int                            curtime = 0;
  vector<pair<int, string> >     arrivals;
  
  // Warshall-Floyd (APSP)
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      if(i == j)
        ; //dist[i][i] = 0, next[i][i] = i;
      else if(dist[i][j] < NOT_CONN)
        next[i][j] = j;
  for(int k = 0; k < N; k++)
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
        if(dist[i][k] > NOT_CONN || dist[k][j] > NOT_CONN) continue;
        else if(dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
          next[i][j] = next[i][k];
        } else if(dist[i][k] + dist[k][j] == dist[i][j] &&
                  next[i][k] < next[i][j]) {
          next[i][j] = next[i][k];
        }
  // Display distance matrices
  ifdebug(8) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++)
        if(dist[i][j] < NOT_CONN)
          debug_print(" %4d-%02d", dist[i][j], 1 + next[i][j]);
        else
          debug_print(" NOTCONN");
      debug_print("\n");
    }
  }
  
  // List parcels
  ifdebug(3) {
    for(int i = 0; i < parcels.size(); i++) {
      debug_print("Parcel id=%s, route %d",
                  parcels[i].id.c_str(), 1 + parcels[i].src);
      int pos = parcels[i].src;
      do {
        pos = next[pos][parcels[i].dest];
        assert(pos >= 0);
        debug_print("-%d", 1 + pos);
      } while(pos != parcels[i].dest);
      debug_print("\n");
    }
  }
  
  // initialize event queue
  for(int i = 0; i < parcels.size(); i++)
    Q.push(event(parcels[i].stime, event::parcel_t, i, parcels[i].src));
  for(int i = 0; i < postman_pos.size(); i++)
    postman_pos[i] = i;

  // simulation loop
  while(! Q.empty()) {
    event e = Q.top(); Q.pop();
    curtime = e.tm;

    // First process events which occurs at the same time
    do {
      switch(e.type) {
      case event::postman_t:
        {
          debug(5, "postman[%d] arrived at po#%d, time=%d\n",
                1 + e.id, 1 + e.place, curtime);
          postman_pos[e.id] = e.place;
        }
        break;
      case event::parcel_t:
        {
          const parcel& p = parcels[e.id];
          debug(5, "parcel[%s] will arrive at po#%d, time=%d\n",
                parcels[e.id].id.c_str(), 1 + e.place, curtime);
          if(parcels[e.id].dest == e.place) {
            // arrived at the destination
            arrivals.push_back(make_pair(curtime, p.id));
          } else {
            // more routing needed
            dispatch_queue[e.place].push_back(make_pair(curtime, e.id));
          }
        }
        break;
      }
      
      if(Q.empty()) goto last_round;
      e = Q.top(); Q.pop();
    } while(e.tm == curtime);
    Q.push(e);
    
  last_round: ;
    // and then decide postman's action
    debug(5, "=== time=%d ===\n", curtime);
    for(int i = 0; i < N; i++) {
      if(postman_pos[i] == i) {
        // The postman is at his home, so check parcel dispatch queue
        if(! dispatch_queue[i].empty()) {
          list<pair<int, int> >& vi = dispatch_queue[i];
          
          // First decide the destination
          int dispatch_to = next[i][parcels[vi.front().second].dest];
          for(list<pair<int, int> >::iterator it = vi.begin(), ie = vi.end();
              it != ie && vi.front().first == it->first;
              ++it)
            // This list is sorted according to the time of arrival (to this PO)
            // So it is enough to check from the front of the queue
            if(next[i][parcels[it->second].dest] < dispatch_to)
              dispatch_to = next[i][parcels[it->second].dest];
          assert(dispatch_to >= 0);
          debug(5, "postman[%d] dispatch to po#%d\n", 1 + i, 1 + dispatch_to);
          
          // and bring all the parcels delivered to the destination
          list<pair<int, int> > newq;
          for(list<pair<int, int> >::iterator it = vi.begin(), ie = vi.end();
              it != ie;
              ++it)
            if(next[i][parcels[it->second].dest] == dispatch_to)
              Q.push(event(curtime + dist[i][dispatch_to], event::parcel_t,
                           it->second, dispatch_to));
            else
              newq.push_back(*it);
          Q.push(event(curtime + dist[i][dispatch_to], event::postman_t,
                       i, dispatch_to));
          swap(vi, newq);
          postman_pos[i] = ON_THE_WAY;
        } else
          debug(5, "postman[%d] has no mail to transfer\n", 1 + i);
      } else if(postman_pos[i] >= 0) {
        // He is not at the home, but at another postoffice
        int j = postman_pos[i];
        debug(5, "postman[%d] currently at po#%d, go back to his office\n",
              1 + i, 1 + j);
        Q.push(event(curtime + dist[j][i], event::postman_t,
                     i, i));
        postman_pos[i] = ON_THE_WAY;
      } else
        // He is now on the way to some postoffice
        debug(5, "postman[%d] on the way\n", 1 + i);
    }
  }
  
  // Display Results
  sort(arrivals.begin(), arrivals.end());
  for(int i = 0; i < arrivals.size(); i++)
    cout << arrivals[i].second << ' ' << arrivals[i].first << endl;
}

static
int usage(const char *self)
{
  cerr << "Usage: " << self << " [-h|--help] [-d debuglevel]" << endl;
  return 1;
}

int main(int argc, char *argv[])
{
  // Parse command-line arguments
  try {
    for(int i = 1; i < argc; i++) {
      if(!strcmp(argv[i], "-h") || !strcmp(argv[i], "--help"))
        return usage(argv[0]);
      else if(!strcmp(argv[i], "-d")) {
        if(++i >= argc) throw "Error: no argument";
        debug_level = atoi(argv[i]);
      } else {
        throw "Error: unknown option";
      }
    }
  } catch(const char *msg) {
    cerr << msg;
    return usage(argv[0]);
  }
  
  // Main loop
  int n, m;
  int ncase = 0;
  while(cin >> n >> m, n || m) {
    vector<vector<int> > dist(n, vector<int>(n, NOT_CONN));
    
    while(m--) {
      int a, b, c; cin >> a >> b >> c;
      --a, --b;
      dist[a][b] = dist[b][a] = c;
    }
    
    int l; cin >> l;
    vector<parcel> parcels;
    while(l--) {
      int f, t, st; string name;
      cin >> f >> t >> st >> name;
      parcels.push_back(parcel(st, name, --f, --t));
    }
    
    if(ncase++) cout << endl;
    debug(1, "********** Test Case #%d **********\n", ncase);
    solve(dist, parcels);
  }
}