/*
  06:38 - 
 */
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
#include<climits>
#include<cstdio>
#include<cmath>
#include<map>
#include<set>
#include<deque>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define LLINF (LLONG_MAX)
#define MAX_V 33
#define MAX_E 500
#define all(n) begin(n),end(n)

using namespace std;

const bool DEBUG = false;

typedef long long ll;
typedef pair<int,string> is;

struct Data{
  ll to,cost;
  Data(ll to=-1,ll cost=-1):to(to),cost(cost){}
  bool operator < (const Data& data)const { return cost > data.cost; }
};

struct Object{
  ll from,to,timer;
  string label;
  ll priority;
  Object(ll from=-1,ll to=-1,ll timer=-1,string label="",ll priority=-1):from(from),to(to),timer(timer),label(label),priority(priority){}
  bool operator < (const Object& obj)const {
    if(priority != obj.priority)return priority < obj.priority;
    if( timer != obj.timer )return timer < obj.timer;
    return to < obj.to;
  }
};

vector<Data> G[MAX_V];
ll mincost[MAX_V][MAX_V];
ll pre[MAX_V][MAX_V];
ll V,E,clist[MAX_V][MAX_V];

void dijkstra(){
  rep(i,V)REP(j,i,V)mincost[i][j] = mincost[j][i] = pre[i][j] = pre[j][i] = LLINF;
  rep(goal,V){
    mincost[goal][goal] = 0;
    priority_queue<Data> Q;
    Q.push(Data(goal,0));
    while(!Q.empty()){
      Data data = Q.top(); Q.pop();
      ll cur = data.to;
      ll cost = data.cost;
      if( mincost[cur][goal] < cost )continue;
      rep(i,(int)G[cur].size()){
	ll next = G[cur][i].to;
	ll ncost = G[cur][i].cost;
	if(mincost[next][goal] >= cost + ncost){
	  if(mincost[next][goal] == cost + ncost) pre[next][goal] = min(pre[next][goal],cur);
	  if(mincost[next][goal] > cost + ncost)  pre[next][goal] = cur;
	  mincost[next][goal] = cost + ncost;
	  Q.push(Data(next,mincost[next][goal]));
	}
      }
    }
  }
  if(DEBUG){
  rep(i,V){
    cout << "from = " << i << endl;
    rep(j,V){
      if( mincost[i][j] == LLINF )continue;
      cout << "to = " << j << " pre[" << i << "][" << j << "] = " << pre[i][j] << " cost = " << mincost[i][j] << endl;
    }
    cout << endl;
  }
  }
}


void simulation(){
  int n;
  cin >> n;
  ll *schedule = new ll[V]; // coefficient
  rep(i,V)schedule[i] = 0;
  deque<Object> *PostOffice = new deque<Object>[V];
  deque<Object> item;
  vector<is> ans;
  rep(i,n){
    ll sp,gp,tm;
    string label;
    cin >> sp >> gp >> tm >> label;
    --sp,--gp;
    item.push_back(Object(sp,gp,tm,label,0));
  }
  sort(all(item));

  ll remain = n;
  ll event_time = -1;
  ll next_pos;
  ll phase = 0;
  ll pe = -1;
  while(remain){
    if(DEBUG)cout << "remain = "  << remain << " let's start--------------------------" << endl;
    event_time = LLINF;
    next_pos = -1;

    if(!item.empty()){
      sort(all(item));
      event_time = item.front().timer;
      if(DEBUG)cout << "event_time first = > " << event_time << endl;
    }

    rep(i,V)if(!PostOffice[i].empty()){
      sort(all(PostOffice[i]));
      rep(j,(int)PostOffice[i].size()){
	if(DEBUG)cout << "check " << event_time << " > " << PostOffice[i][j].timer + mincost[i][pre[i][PostOffice[i][j].to]] << " ? " << endl;
	if( event_time > PostOffice[i][j].timer+mincost[i][pre[i][PostOffice[i][j].to]]){
	    event_time = PostOffice[i][j].timer+mincost[i][pre[i][PostOffice[i][j].to]];
	    if(DEBUG)cout << " new time : " << event_time << endl;
	    next_pos = i;
	}
      }
    }
    if( pe != event_time ){
      phase++;
    }
    pe = event_time;
    if(DEBUG)cout << "event_time = " << event_time << endl;
    if( !item.empty() && event_time == item.front().timer){

      while( !item.empty() && item.front().timer == event_time){
	Object obj = item.front(); item.pop_front();
	if( obj.from == obj.to ){
	  ans.push_back(is(obj.timer,obj.label));
	  remain--;
	  if(DEBUG)cout << "finish! " << obj.label << " : " << obj.timer << endl;
	  continue;
	}

	if(DEBUG)cout << "push | from : " << obj.from << ", to : " << obj.to << " " << obj.label  << " (" << obj.timer << "," << obj.priority << ")" << endl;
	//if(obj.timer > schedule[obj.from])schedule[obj.from] = obj.timer;


	obj.timer = max(obj.timer,schedule[obj.from]);
	obj.priority = phase;
	PostOffice[obj.from].push_back(obj);
	if(DEBUG)cout << "QUEUE " << obj.from << endl;
	sort(all(PostOffice[obj.from]));
	if(DEBUG){
	  rep(j,PostOffice[obj.from].size()){
	    cout << PostOffice[obj.from][j].label << "(" << PostOffice[obj.from][j].timer << "," << PostOffice[obj.from][j].priority << ") " ;
	  } cout << endl;
	}
	//sort(PostOffice[obj.from].begin(),PostOffice[obj.from].end());
      }
      continue;
    }
    if(DEBUG)cout << " ----------- " << remain << endl;

    assert(next_pos != -1);

    vector<Object> use,tmp;
    ll dest = PostOffice[next_pos].front().to;
    if(DEBUG)cout << "THE TOP : " << PostOffice[next_pos].front().label << endl;
    //int cur  = PostOffice[next_pos].front().from;
    ll current_time = PostOffice[next_pos].front().timer;
    for(Object& obj : PostOffice[next_pos]){
      if( current_time >= obj.timer &&  pre[next_pos][dest] == pre[obj.from][obj.to] ){
	use.push_back(obj);
      } else {
	tmp.push_back(obj);
      }
    }
    PostOffice[next_pos].clear();
    rep(j,(int)tmp.size()){
      tmp[j].timer = max(tmp[j].timer,use[0].timer+mincost[next_pos][pre[next_pos][dest]]*2);
      if(DEBUG)cout << "again,push  " << tmp[j].label << " time : " << tmp[j].timer << " again to " << next_pos << endl;
      //item.push_back(tmp[j]);
      PostOffice[next_pos].push_back(tmp[j]);
    }
    //sort(all(item));
    schedule[next_pos] = use[0].timer+mincost[next_pos][pre[next_pos][dest]]*2;
    //if(DEBUG)cout << "Aschedule[" << next_pos << "] = " << schedule[next_pos] << endl;
    rep(j,(int)use.size()){
      if(DEBUG)cout << "transport from " << next_pos << " to " << pre[next_pos][dest] <<  " : "  << use[j].label << " cost = "; 
      use[j].timer += /*schedule[next_pos] +*/ mincost[next_pos][pre[next_pos][dest]];
      if(DEBUG)cout << use[j].timer << endl;
      use[j].from = pre[next_pos][dest];
      use[j].priority = -1;
      item.push_back(use[j]);
    }

    /*
    rep(i,V){
      //cout << "schedule[" << i << "] " << schedule[i] << endl;
      if( schedule[i] > event_time ) continue;
      //cout << "post -> " << i << endl;
      vector<Object> use,tmp;
      int next = IINF;
      for(Object& obj : PostOffice[i]){
	if( next == IINF ){
	  next = obj.to;
	  use.push_back(obj);
	  continue;
	}
	if( obj.to == next ) use.push_back(obj);
	else                 tmp.push_back(obj);
      }
      //rep(j,(int)use.size())cout << " --> " << use[j].from << "," << use[j].to << " " << use[j].timer << " " << use[j].label << endl;
      PostOffice[i].clear();
      rep(j,(int)tmp.size())PostOffice[i].push_back(tmp[j]);
      if( next == IINF )continue;
      if( schedule[i] < use[0].timer ) schedule[i] = use[0].timer;
      schedule[i] += clist[i][pre[i][next]];
      rep(j,(int)use.size()){
	use[j].timer = schedule[i];
	use[j].from = pre[i][next];
	item.push_back(use[j]);
      }

    }
    */
  }
  delete [] schedule;
  delete [] PostOffice;
  sort(all(ans));
  rep(i,(int)ans.size()){
    cout << ans[i].second << " " << ans[i].first << endl;
  }
}


int main(){
  bool F = true;
  while(cin >> V >> E, V|E){
    if(!F)puts("");
    F = false;
    rep(i,V)G[i].clear();
    rep(i,V)rep(j,V)clist[i][j] = LLINF;
    rep(i,E){
      int a,b,cost;
      cin >> a >> b >> cost;
      a--,b--;
      G[a].push_back(Data(b,cost));
      G[b].push_back(Data(a,cost));
      clist[a][b] = clist[b][a] = cost;
    }

    dijkstra();

    simulation();

  }
  return 0;
}

Measured memory_bytes: 1500