#include<iostream>
#include<climits>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb         push_back
#define mp         make_pair
#define ALL(C)     (C).begin(),(C).end()

const int N = 32;
const int inf = INT_MAX;
const int costinf=(1<<21);


typedef struct{string name;int time,tar;}Mail;

class Postman{
public:
  int time,tar;
  vector<Mail> mail;
};

int cost[N][N];
int edge[N][N];//costinf
int next[N][N];
void wf(int n){
  rep(i,n)rep(j,n)cost[i][j]=edge[i][j];
  rep(k,n)rep(i,n)rep(j,n)cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);

  rep(i,n){
    rep(j,n){
      next[i][j]=100;
      if (i == j)continue;
      rep(k,n){
	if (i == k)continue;
	if (edge[i][k] == costinf)continue;
	if (cost[i][j] == edge[i][k]+cost[k][j]){
	  next[i][j]=k;
	  break;
	}
      }
    }
  }
}

class Postoffice{
public:
  vector<Mail> mail;
  int find_next_time(int node,int now){
    int mintime=inf;
    rep(i,mail.size()){
      if (mail[i].time < now)return 0;
      else mintime=min(mintime,mail[i].time);
    }
    if (mintime == inf)return mintime;
    return mintime-now;
  }

  void set_man(int node,int now,Postman &man){
    int mintime=inf,mindex=100;
    rep(i,mail.size()){
      if (mail[i].time > now)continue;
      if (mail[i].time < mintime || 
	  (mintime == mail[i].time && next[node][mail[i].tar] < mindex)){
	mintime=mail[i].time;
	mindex =next[node][mail[i].tar];
      }
    }
    
    if (mindex == 100)return;

    rep(i,mail.size()){
      if (mail[i].time > now)continue;
      if (next[node][mail[i].tar] == mindex){
	man.mail.pb(mail[i]);
	mail.erase(mail.begin()+i);
	i--;
      }
    }
    
    man.time=edge[node][mindex];
    man.tar =mindex;
  }
};


void solve(int n,Postman *man,Postoffice *office){
  vector<pair<int ,string> > ans;
  int t = 0;

  //initialization
  wf(n);

  while(true){
    int minevent=inf;
    
    // arrive
    rep(i,n){
      if (man[i].tar != -1)minevent=min(minevent,man[i].time);
    }

    rep(i,n){
      if (man[i].tar == -1){
	minevent=min(office[i].find_next_time(i,t),minevent);
      }
    }

    if (minevent == inf)break;

    t+=minevent;
    
    rep(i,n){
      if (man[i].tar != -1){
	man[i].time-=minevent;
	if (man[i].time == 0){
	  if (man[i].tar != i){
	    rep(j,man[i].mail.size()){
	      if (man[i].tar == man[i].mail[j].tar){
		ans.pb(mp(t,man[i].mail[j].name));
	      }
	      else {
		man[i].mail[j].time=t;
		office[man[i].tar].mail.pb(man[i].mail[j]);
	      }
	    }
	    man[i].mail.clear();
	    man[i].time=edge[man[i].tar][i];
	    man[i].tar=i;
	  }else if (man[i].tar == i){
	    man[i].tar=-1;
	  }
	}
      }
    }

    rep(i,n){
      if (man[i].tar != -1)continue;
      office[i].set_man(i,t,man[i]);
    }
  }

  sort(ALL(ans));
  rep(i,ans.size()){
    cout << ans[i].second <<" " << ans[i].first << endl;
  }
}

main(){
  int n,m;
  int te=0;
  while(cin>>n>>m && n){
    if (te)cout<<endl;
    te++;
    rep(i,n){
      rep(j,n)edge[i][j]=costinf;
      edge[i][i]=0;
    }
    Postman    man[n];
    Postoffice     office[n];
    rep(i,n)man[i].tar=-1;
    
    
    rep(i,m){
      int f,t,c;
      cin>>f>>t>>c;
      f--;t--;
      edge[f][t]=edge[t][f]=c;
    }
    
    int l;
    cin>>l;
    rep(i,l){
      int fr,to,ti;
      string name;
      cin>>fr>>to>>ti>>name;
      office[fr-1].mail.pb((Mail){name,ti,to-1});
    }
    
    solve(n,man,office);
  }
}

Measured memory_bytes: 1164