#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 32;

const int INF = 1 << 30;

const string evnms[] = { "E_LT_ARV", "E_PM_BK", "E_PM_DL", "E_PM_ST" };

/* typedef */

typedef pair<int,int> pii;
typedef pair<int,string> pis;
typedef vector<int> vi;
typedef vector<pis> vpis;
typedef queue<pii> qpii;

struct Letter {
  int t, nexthop, dst;
  string label;
  Letter() {}
  Letter(int _t, int _nexthop, int _dst, string _label) {
    t = _t, nexthop = _nexthop, dst = _dst, label = _label;
  }

  bool operator<(const Letter& lt) const {
    return t < lt.t || (t == lt.t && nexthop < lt.nexthop);
  }

  void print() {
    printf("    Letter: t=%d, nexthop=%d, dst=%d, labe=%s\n",
	   t, nexthop, dst, label.c_str());
  }
};

typedef deque<Letter> dql;

struct PostMan {
  int id, st;
  dql mls;

  void print() {
    printf("  PostMan: id=%d, st=%d, mls=%lu\n", id, st, mls.size());
    for (int i = 0; i < mls.size(); i++) mls[i].print();
  }
};

enum { M_WT, M_ON };
enum { E_LT_ARV, E_PM_BK, E_PM_DL, E_PM_ST };

struct Event {
  int t, st;
  int p0, p1;
  string label;
  PostMan *pm;

  Event() {}
  Event(int _t, int _st, int _p0, int _p1, string _label) {
    t = _t, st = _st, p0 = _p0, p1 = _p1;
    label = _label;
    pm = NULL;
  }
  Event(int _t, int _st, int _p0, int _p1, PostMan *_pm) {
    t = _t, st = _st, p0 = _p0, p1 = _p1;
    label = "";
    pm= _pm;
  }
  
  bool operator>(const Event& ev) const {
    return t > ev.t || (t == ev.t && st > ev.st);
  }

  void print() {
    if (st == E_LT_ARV) {
      printf("Event: t=%d, st=%s, %d->%d, label=%s\n",
	     t, evnms[st].c_str(), p0, p1, label.c_str());
    }
    else {
      printf("Event: t=%d, st=%s, %d->%d, pm=%d\n",
	     t, evnms[st].c_str(), p0, p1, pm->id);
      pm->print();
    }
  }
};

/* global variables */

int n, m, l;
vi nbrs[MAX_N];
int costs[MAX_N][MAX_N];
int dists[MAX_N], nhops[MAX_N];
int rt[MAX_N][MAX_N];

dql posts[MAX_N];
PostMan pmen[MAX_N];

/* subroutines */

/* main */

int main() {
  for (bool first = true;; first = false) {
    cin >> n >> m;
    if (n == 0) break;
    
    if (! first) cout << endl;

    for (int i = 0; i < n; i++) nbrs[i].clear();
    
    for (int i = 0; i < m; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      a--, b--;
      nbrs[a].push_back(b);
      nbrs[b].push_back(a);
      costs[a][b] = costs[b][a] = c;
    }

    for (int i = 0; i < n; i++) {
      sort(nbrs[i].begin(), nbrs[i].end());
      for (int j = 0; j < n; j++) rt[i][j] = -1;
    }

    for (int st = 0; st < n; st++) {
      for (int i = 0; i < n; i++) dists[i] = INF;
      dists[st] = 0;
      nhops[st] = -1;

      qpii q;
      q.push(pii(0, st));

      while (! q.empty()) {
	pii u = q.front();
	q.pop();

	int ud = u.first;
	int ui = u.second;
	if (ud != dists[ui]) continue;

	int unhop = nhops[ui];
	vi& nbru = nbrs[ui];

	for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	  int vi = *vit;
	  int vd = ud + costs[ui][vi];
	  if (dists[vi] > vd) {
	    dists[vi] = vd;
	    nhops[vi] = (unhop >= 0) ? unhop : vi;
	    q.push(pii(vd, vi));
	  }
	  else if (dists[vi] == vd && nhops[vi] > unhop) {
	    dists[vi] = vd;
	    nhops[vi] = unhop;
	    q.push(pii(vd, vi));
	  }
	}
      }

      for (int gl = 0; gl < n; gl++) rt[st][gl] = nhops[gl];
    }

    if (false) {
      for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) cout << rt[i][j] << ' ';
	cout << endl;
      }
    }

    for (int i = 0; i < n; i++) {
      posts[i].clear();
      pmen[i].id = i, pmen[i].st = M_WT;
      pmen[i].mls.clear();
    }

    priority_queue<pis,vector<pis>,greater<pis> > arrived;
    priority_queue<Event,vector<Event>,greater<Event> > pqe;

    cin >> l;
    
    for (int i = 0; i < l; i++) {
      int p0, p1, t;
      string label;
      cin >> p0 >> p1 >> t >> label;
      p0--, p1--;
      
      pqe.push(Event(t, E_LT_ARV, p0, p1, label));
    }

    while (! pqe.empty()) {
      Event ev = pqe.top();
      pqe.pop();
      //ev.print();
      
      if (ev.st == E_LT_ARV) {
	int nexthop = rt[ev.p0][ev.p1];
	posts[ev.p0].push_back(Letter(ev.t, nexthop, ev.p1, ev.label));

	PostMan *pm = &pmen[ev.p0];
	if (pm->st == M_WT) {
	  pm->st = M_ON;
	  pqe.push(Event(ev.t, E_PM_ST, ev.p0, ev.p0, pm));
	}
      }

      else if (ev.st == E_PM_ST) {
	dql& post = posts[ev.p0];
	sort(post.begin(), post.end());

	Letter lt0 = post.front();
	post.pop_front();
	PostMan *pm = ev.pm;
	pm->mls.push_back(lt0);

	for (dql::iterator lit = post.begin(); lit != post.end();) {
	  if (lit->nexthop == lt0.nexthop) {
	    pm->mls.push_back(*lit);
	    lit = post.erase(lit);
	  }
	  else lit++;
	}

	pqe.push(Event(ev.t + costs[ev.p0][lt0.nexthop],
		       E_PM_DL, ev.p0, lt0.nexthop, pm));
      }

      else if (ev.st == E_PM_DL) {
	PostMan *pm = ev.pm;
	dql& mls = pm->mls;
	
	for (dql::iterator lit = mls.begin(); lit != mls.end(); lit++) {
	  lit->nexthop = rt[ev.p1][lit->dst];
	  if (lit->nexthop == -1)
	    arrived.push(pis(ev.t, lit->label));
	  else
	    pqe.push(Event(ev.t, E_LT_ARV, ev.p1, lit->dst, lit->label));
	}

	pm->mls.clear();

	pqe.push(Event(ev.t + costs[ev.p1][ev.p0],
		       E_PM_BK, ev.p1, ev.p0, pm));
      }

      else if (ev.st == E_PM_BK) {
	PostMan *pm = ev.pm;
	if (posts[pm->id].empty())
	  pm->st = M_WT;
	else {
	  pqe.push(Event(ev.t, E_PM_ST, ev.p1, ev.p1, pm));
	}
      }
    }

    //cout << arrived.size() << endl;

    while (! arrived.empty()) {
      pis lt = arrived.top();
      arrived.pop();

      cout << lt.second << ' ' << lt.first << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1476