#include <bits/stdc++.h>
#define INF 10000000
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,string> P2;

struct edge{
	int t,c;
	edge(){}
	edge(int tt,int cc){
		t=tt;
		c=cc;
	}
};

struct data{
	int f,id;
	int ti,gt,next;
	data(){}
	data(int ff,int ii,int tt,int gg,int nn){
		f=ff;
		id=ii;
		ti=tt;
		gt=gg;
		next=nn;
	}
	bool operator<(const data& d)const{
		if(ti==d.ti){
			if(gt==d.gt)return next>d.next;
			return gt>d.gt;
		}
		return ti>d.ti;
	}
};

int n,m,l;
vector<edge> G[1001];

int dist[33];
int dijk(int f,int t){
	fill(dist,dist+n,INF);
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,t));
	int res=n;
	dist[t]=0;
	while(que.size()){
		P p=que.top();
		que.pop();
		if(dist[p.second]<p.first)continue;
		for(int j=0;j<G[p.second].size();j++){
			edge e=G[p.second][j];
			if(e.t==f && dist[e.t]==dist[p.second]+e.c)res=min(res,p.second);
			if(dist[e.t]>dist[p.second]+e.c){
				if(e.t==f)res=p.second;
				dist[e.t]=dist[p.second]+e.c;
				que.push(P(dist[e.t],e.t));
			}
		}
	}
	return res;
}

priority_queue<data> que[35];
string str[1001];
int lf[1001],lt[1001],ltime[1001];
int next[35];
int ntime[35];
priority_queue<P,vector<P>,greater<P> > backer;
vector<P2> res;

int main(void){
	bool space=false;
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		if(space)cout << endl;
		for(int i=0;i<n;i++){
			G[i].clear();
		}
		space=true;
		for(int i=0;i<m;i++){
			int f,t,c;
			scanf("%d%d%d",&f,&t,&c);
			f--;
			t--;
			G[f].push_back(edge(t,c));
			G[t].push_back(edge(f,c));
		}
		for(int i=0;i<n;i++){
			while(que[i].size())que[i].pop();
		}
		while(backer.size())backer.pop();
		scanf("%d",&l);
		for(int i=0;i<l;i++){
			cin >> lf[i] >> lt[i] >> ltime[i] >> str[i];
			lf[i]--;
			lt[i]--;
			que[lf[i]].push(data(-1,i,ltime[i],ltime[i],dijk(lf[i],lt[i])));
		}
		memset(next,0,sizeof(next));
		memset(ntime,0,sizeof(ntime));
		res.clear();
		while(1){
			bool flag=false;
			int best=0,bt=0;
			for(int i=0;i<n;i++){
				if(que[i].size()>0){
					data p=que[i].top();
					if(!flag){
						best=p.ti;
						bt=i;
					}
					flag=true;
					if(best>p.ti){
						bt=i;
						best=p.ti;
					}
				}
			}
			if(!flag)break;
			data v=que[bt].top();
			que[bt].pop();
			while(backer.size()){
				P p=backer.top();
				if(p.first<=v.ti){
					backer.pop();
					next[p.second]=0;
				}else break;
			}
			if(bt==lt[v.id]){
				res.push_back(P2(v.ti,str[v.id]));
				continue;
			}
			if(next[bt]==-1){
				v.ti=ntime[bt];
				que[bt].push(v);
				continue;
			}
			int nex=dijk(bt,lt[v.id]);
			int now=v.ti;
			int plu=0;
			for(int i=0;i<G[bt].size();i++){
				if(nex==G[bt][i].t)plu=G[bt][i].c;
			}
			next[bt]=-1;
			ntime[bt]=v.ti+plu*2;
			backer.push(P(v.ti+plu*2,bt));
			v.ti+=plu;
			que[nex].push(data(bt,v.id,v.ti,v.ti,(nex==lt[v.id])?-1:dijk(nex,lt[v.id])));
			queue<data> tmp;
			while(que[bt].size()){
				data pp=que[bt].top();
				if(pp.ti>now)break;
				que[bt].pop();
				if(pp.next==nex){
					que[nex].push(data(bt,pp.id,v.ti,v.ti,(nex==lt[pp.id])?-1:dijk(nex,lt[pp.id])));
				}else{
					tmp.push(pp);
				}
			}
			while(tmp.size()){
				data pp=tmp.front();
				que[bt].push(pp);
				tmp.pop();
			}
		}
		sort(res.begin(),res.end());
		for(int i=0;i<res.size();i++){
			cout << res[i].second << " " << res[i].first << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3424