#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define REP(i, s, e) for ( int i = s; i <= e; i++ )  

struct Edge{
	int a,b,c;
	Edge(int a,int b,int c) : a(a),b(b),c(c){}
};

vector<Edge> v[32];
int next[1000][32];
string name[1000];


struct Info{
	int id;
	int pos;
	int time;
	int otodoke;
	Info(){}
	Info(int id,int pos,int time,int otodoke) : id(id),pos(pos),time(time),otodoke(otodoke){}
};

bool operator < (const Info &a,const Info &b){
	if( a.time != b.time ) return a.time > b.time ;
	if( a.pos != b.pos ) return a.pos > b.pos;
	if( a.otodoke != b.otodoke ) return a.otodoke > b.otodoke;
	return next[a.id][a.pos] > next[b.id][b.pos];
}


int main(){
	int blflg=0;
	int n,m;
	while(cin >> n >> m && n){
		for(int i = 0 ; i < 32 ; i++)
			v[i].clear();
		if(blflg++)cout << endl;
		long long wf[100][100];
		for(int i = 0 ; i < 100 ; i++){
			for(int j = 0 ; j < 100 ; j++){
				wf[i][j] = i==j?0:1e10;
			}
		}
		
		priority_queue<Info> Q;
		for(int i = 0 ; i < m ; i++){
			int a,b,c;
			cin >> a >> b >> c;
			a--,b--;
			wf[a][b] = c;
			wf[b][a] = c;
			v[a].push_back(Edge(a,b,c));
			v[b].push_back(Edge(b,a,c));
		}
		for(int i = 0 ; i < n ; i++){
			for(int j = 0 ; j < n ; j++){
				for(int k = 0 ; k < n ; k++){
					wf[j][k] = min(wf[j][k],wf[j][i]+wf[i][k]);
				}
			}
		}
		int l;
		cin >> l;
		for(int i = 0 ; i < l ; i++){
			int a,b,t;
			cin >> a >> b >> t >> name[i];
			a--,b--;
			int cur = a;
			while( cur != b ){
				next[i][cur] = 1e9;
				for(int j = 0 ; j < v[cur].size() ; j++){
					if( wf[cur][b] == wf[v[cur][j].b][b]+v[cur][j].c ){
						next[i][cur] = min(next[i][cur],v[cur][j].b);
						
					}
				}
				cur = next[i][cur];
			}
			next[i][cur] = -1;
			Q.push(Info(i,a,t,t));
		}
		vector< pair<int,string> > sorted;
		
		int waiting[32]={};
		
		int prev = 0;
		while(Q.size()){
			Info q = Q.top();
			
			//cout << "[" << q.time << "]" << name[q.id] << " " << q.pos  << " " << q.otodoke << endl;
			for(int i = 0 ; i < n ; i++){
				waiting[i] = max(waiting[i]-(q.time-prev),0);
			}
			prev = q.time;
			vector<Info> chk;
			vector<Info> dummy;
			while(Q.size() && Q.top().time == q.time && Q.top().pos == q.pos ){
				if( next[Q.top().id][Q.top().pos] == next[q.id][q.pos] ){
					chk.push_back(Q.top());
				}else{
					dummy.push_back(Q.top());
				}
				Q.pop();
			}
			for(int i = 0 ; i < dummy.size() ; i++)
				Q.push(dummy[i]);
			
			if( next[q.id][q.pos] == -1 ){
				for(int i = 0 ; i < chk.size() ; i++){
					sorted.push_back(make_pair(chk[i].otodoke,name[chk[i].id]));
				}
				continue;
			}
			if( waiting[q.pos] ){
				for(int i = 0 ; i < chk.size() ; i++){
					Q.push(Info(chk[i].id,chk[i].pos,chk[i].time+waiting[q.pos],chk[i].otodoke));
				}
				continue;
			}
			for(int i = 0 ; i < chk.size() ; i++){
				//cout << chk[i].pos << " " << next[chk[i].id][chk[i].pos] << " < " << endl;
				int cst = wf[chk[i].pos][next[chk[i].id][chk[i].pos]];
				Q.push(Info(chk[i].id,next[chk[i].id][chk[i].pos],chk[i].time+cst,chk[i].time+cst));
				waiting[q.pos] = 2*cst;
			}
		}
		sort(sorted.begin(),sorted.end());
		for(int i = 0 ; i < sorted.size() ; i++)
			cout << sorted[i].second << " " << sorted[i].first << endl;
	}
		
}

Measured memory_bytes: 1588