#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Edge{
  int src, dst, cost;
  Edge() {}
  Edge(int s, int d, int c) : src(s), dst(d), cost(c) {}
};

typedef vector<Edge> Node;
typedef vector<Node> Graph;
struct Event{
  int type;
  int time;
  int latter;
  int office;
  Event(int ty, ll t, int l, int o) : 
    type(ty), time(t), latter(l), office(o) {}
  bool operator < (const Event& e) const {
    if(time != e.time) return time < e.time;
    if(type != e.type) return type < e.type;
    if(office != e.office) return office < e.office;
    return latter < e.latter;
  }
  bool operator > (const Event& e) const {
    if(time != e.time) return time > e.time;
    if(type != e.type) return type > e.type;
    if(office != e.office) return office > e.office;
    return latter > e.latter;
  }
};
struct Latter{
  string name;
  int src, dst;
};
typedef pair<int, string> P;

void do_send(Event& e, vector<Event>& lq, priority_queue<Event, vector<Event>, greater<Event> >& que, int dist[36][36], vector<bool>& wait){
  Event se = lq.front();
  lq.erase(lq.begin());
  que.push(Event(0, e.time + dist[e.office][se.office], se.latter, se.office));
  for(vector<Event>::iterator it = lq.begin(); it != lq.end(); ){
    if(it->office == se.office){
      que.push(Event(0, e.time + dist[e.office][se.office], it->latter, se.office));
      it = lq.erase(it);
    }else{
      it++;
    }
  }
  que.push(Event(1, e.time + 2 * dist[e.office][se.office], -1, e.office));
  wait[e.office] = false;
}
int main(){
  int N, M;
  bool first = true;
  while(cin >> N >> M && N){

    if(first) first = false;
    else cout << endl;

    Graph G(N);
    REP(i, M){
      int a, b, c;
      cin >> a >> b >> c;
      a--; b--;
      G[a].push_back(Edge(a, b, c));
      G[b].push_back(Edge(b, a, c));
    }
    int dist[36][36] = {};
    REP(i, N) REP(j, N) dist[i][j] = (i != j) ? INF : 0;
    REP(i, N) FORIT(e, G[i]) dist[e->src][e->dst] = e->cost;
    REP(k, N) REP(i, N) REP(j, N) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // next[i][j] := 現在地i, 目的地jの郵便物の次の行き先
    int next[36][36] = {};
    memset(next, -1, sizeof(next));
    REP(i, N) REP(j, N) if(i != j && !G[i].empty() && dist[i][j] < INF){
      next[i][j] = INF;
      int edge_cost = -1;
      FORIT(e, G[i]){
        if(e->cost + dist[e->dst][j] == dist[i][j] && next[i][j] > e->dst){
          next[i][j] = e->dst;
          edge_cost = e->cost;
        }
      }
    }

    int L; cin >> L;
    vector<Latter> latters(L);
    priority_queue<Event, vector<Event>, greater<Event> > que;
    vector< vector<Event> > l_que(N);
    REP(i, L){
      ll time;
      cin >> latters[i].src >> latters[i].dst >> time >> latters[i].name;
      latters[i].src--; latters[i].dst--;
      que.push(Event(0, time, i, latters[i].src));
    }
    vector<P> answer;
    vector<bool> wait(N, true);
    while(!que.empty()){
      Event e = que.top(); que.pop();
      vector<Event>& lq = l_que[e.office];
      if(e.type == 0){
        Latter& l = latters[e.latter];
        if(l.dst == e.office){
          answer.push_back(P(e.time, l.name));
        }else{
          int to = next[e.office][l.dst];
          assert(to != -1);
          Event send(0, e.time, e.latter, to);
          lq.insert(lower_bound(lq.begin(), lq.end(), send), send);
        }
      }else if(e.type == 1){
        wait[e.office] = true;
      }
      if(wait[e.office] && !lq.empty() && (que.empty() || e.time != que.top().time || e.office != que.top().office)){
        do_send(e, lq, que, dist, wait);
      }
    }
    sort(answer.begin(), answer.end());
    REP(i, answer.size()){
      printf("%s %d\n", answer[i].second.c_str(), answer[i].first);
    }
  }
  return 0;
}

Measured memory_bytes: 1472