//TLE
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;

struct packet{
	int tm,pos,dist;
	string name;
	packet(int t,int p,int d,const string&n):
		tm(t),pos(p),dist(d),name(n){}
};
vector<packet> pac;
int len[33][33],to[33][33],bac[33];
int tbl[1001];
const int inf = 1e9;
struct cmp{
	bool operator()	(int x,int y) const
	{
		const packet &a = pac[x], &b = pac[y];
		return a.tm == b.tm
			? to[a.pos][a.dist] > to[b.pos][b.dist]
			: a.tm > b.tm;
	}
};
bool cmp2(int x,int y){
	const packet &a=pac[x], &b = pac[y];
	return a.tm==b.tm ? a.name < b.name: a.tm < b.tm;
}

int main(){
	int n,m,f,t,d,i,j,k,l;
	string name;
	priority_queue<int,vector<int>,cmp> qu;
	for(;cin>>n>>m,n;){
		pac.clear();
		if(**len==1)cout<<endl;

		for(i=0;i<=n;i++){
			for(j=0;j<=m;j++){
				len[i][j]=inf;
				to[i][j]=-1;
			}
			bac[i]=len[i][i]=0;
			to[i][i]=i;
		}

		for(;m--;){
			cin>>f>>d>>t;
			len[f][d] = t;
			len[d][f] = t;
			to[f][d] = d;
			to[d][f] = f;
		}

		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++){
					t = len[i][k] + len[k][j];
					if( len[i][j] > t ){
						len[i][j] = t;
						to[i][j] = to[i][k];
					}
				}
		cin>>l;
		for(j=0;j<l;j++){
			cin>>f>>d>>t>>name;
			pac.push_back( packet(t,f,d,name) );
			qu.push(j);
		}

		for(;!qu.empty();){
			int pi = qu.top();
			packet *p = &pac[pi];
			t = p->tm;
			f = p->pos;
			if( f == p->dist ){
				qu.pop();
				continue;
			}
			if( t < bac[f] ){
				p->tm = bac[f];
				qu.pop();
				qu.push(pi);
			}else{
				d = to[f][p->dist];
				bac[f] = t + 2 * len[p->pos][d];
				for(;;){
					int qi = qu.top();
					packet*q = &pac[qi];
					if(t==q->tm && f==q->pos && to[q->pos][q->dist] == d){
						qu.pop();
						q->tm = max( q->tm + len[f][d], bac[d] );
						q->pos = d;
						qu.push(qi);
					}
					else break;
				}
			}
		}
//		sort(pac.begin(),pac.end(),cmp2);
//		for(j=0;j<l;j++)cout<<pac[j].name<<' '<<pac[j].tm<<endl;
		for(j=0;j<l;j++)tbl[j]=j;
		sort(tbl,tbl+l,cmp2);
		for(j=0;j<l;j++)printf("%s %d\n",pac[tbl[j]].name.c_str(),pac[tbl[j]].tm);

		**len = 1;
	}
}