
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



#ifdef PROFILE
#include <time.h>
#define time _time
#endif

#define MAX_LEN 64

#define MAX_NODE 32
#define MAX_MAIL 1000
#define MAX_LABEL 50+1

#define MAX_TIME (1<<31)
#define MAX_DIST 10000
#define MAX_DISTSUM 320000

#define TRUE 1
#define FALSE 0

typedef enum {
	NONE, /* Í¯çêÄ¢È¢ */
	POST, /* XÖÇÉ é */
	DELI, /* zB */
	DONE  /* zB®¹ */
} MailState;

typedef enum {
	HERE, /* zBõª¢é */
	GO,   /* zBõªÚInÉü©ÁÄ¢é */
	BACK  /* zBõªÚIn©çAÁÄ«Ä¢é */
} NodeState;

typedef struct _Mail{
	MailState state;    /* [ÌóÔ */
	unsigned long timer;          /* XÖÇÉÍ­Ô */
	struct _Mail *next; /* ÉÍ¢½[ */
	int src;            /* a©èê */
	int dst;            /* ÅIÍ¯æ */
	char label[MAX_LABEL]; /* x */
} Mail;

typedef struct {
	NodeState state;    /* zBõÌóÔ */
	unsigned long timer;          /* zBõªÚ®µIíéÔ */
	int dst;            /* zBõÌÚIn */
	short dist[MAX_NODE]; /* ]oHÌ£ */
	char distf[MAX_NODE]; /* ÅZ£vZÏÝtO*/
	int distnext[MAX_NODE]; /* ÅZ£ÌÆ«É^Ôm[h*/
	Mail *post_queue;        /* Í¢Ä¢é[ */
	Mail *deli_queue;        /* zBÌ[ */
} Node;

/* nÂÌXÖÇim[hjÌú» */
void init_nodes(int n);

/* Í¯çêÄ¢È¢[Ì */
int check_mail(int l);
/* XÖÇÔÌÅZ£vZ */
int calc_dist(int a, int b);
/* èzBJn */
void take_mail(int n);
/* [Ì */
void post_mail(Mail *m);
/* zB®¹ */
void arrive_mail(int n);
/* zBõÌAÒõ */
void go_back(int n);
/* zB®¹[Ì\¦ */
void print_arrive(void);


void del_mail(Mail **q,Mail *mail);
void add_mail(Mail **q,Mail *mail);

int compare_mail(const void* a, const void* b);

Node node[MAX_NODE]; /* XÖÇXg */
int node_num; /* XÖÇgp */
Mail mail[MAX_MAIL]; /* [Xg */
int mail_num; /* [gp */
int posted; /* ÏÝ[Ô */
Mail *arrive[MAX_MAIL];/* zB®¹[Xg */
int arrive_cnt;/* zB®¹[ */

unsigned long time = 0; /* V~[VÔ */

int main(){
	char buf[MAX_LEN];
	int i;
	int n,m;
	int a,b,d;
	int l;
	unsigned long min; /* ñ­Î·é^C}l */
#ifdef PROFILE
	clock_t c_input=0, c_init=0, c_all=0, c_sim=0, c_take=0, c_arrive=0, c_mail=0, c_print=0;

	c_all-=clock();
#endif
	
	while(fgets(buf,MAX_LEN,stdin)!=NULL){
		if(sscanf(buf,"%d %d",&n,&m)<2){
			fprintf(stderr,"error:invalid input\n");
		}else{
			/* 0 0 ¾Á½çI¹ */
			if(n<2||m<1)break;
			/* KvÈª¾¯ú» */
#ifdef PROFILE
			c_init-=clock();
#endif
			init_nodes(n);
#ifdef PROFILE
			c_init+=clock();
			c_input-=clock();
#endif
			/* ]oHÇÝæè */
			for(i=0;i<m;i++){
				if(fgets(buf,MAX_LEN,stdin)==NULL)return 0;
				if(sscanf(buf,"%d %d %d",&a,&b,&d)<3)return 0;
				/* 0IWÉ·é½ß-1 */
				node[a-1].dist[b-1] = d;
				node[b-1].dist[a-1] = d;
				node[a-1].distnext[b-1] = b-1;
				node[b-1].distnext[a-1] = a-1;
			}
			/* [ÇÝæè */
			if(fgets(buf,MAX_LEN,stdin)==NULL)return 0;
			if(sscanf(buf,"%d",&l)<1)return 0;
			/* [îñÇÝæè */
			min = MAX_TIME;/* ÅÉ­Î·é^C}Í[ */
			for(i=0;i<l;i++){
				if(fgets(buf,MAX_LEN,stdin)==NULL)return 0;
				if(sscanf(buf,"%d %d %d %[a-zA-Z0-9-_]",
					&(mail[i].src),&(mail[i].dst),&(mail[i].timer),mail[i].label)<4)return 0;
				/* 0IWÉ·é½ß-1 */
				mail[i].src--;
				mail[i].dst--;
				mail[i].state = NONE;
				mail[i].next = NULL;
				if(min>mail[i].timer)min = mail[i].timer;
			}
			node_num = n;
			mail_num = l;
#ifdef PROFILE
			c_input+=clock();
			c_sim-=clock();
#endif

			/* V~[VJn */
			time = min;
			arrive_cnt = 0;
			posted = 0;
			while(check_mail(l)!=0){/* S[ªzBI¹·éÜÅ */
				min = MAX_TIME;
#ifdef PROFILE
				c_mail-=clock();
#endif
				/* èªÍ­ */
				for(i=posted;mail[i].timer==time;i++){
					post_mail(&mail[i]);
					posted++;
				}
				if(posted<mail_num)	min = mail[posted].timer;
#ifdef PROFILE
				c_mail+=clock();
#endif
				for(i=0;i<n;i++){
					/* zBõª·é */
					if(node[i].timer == time){
						if(node[i].state == GO){
#ifdef PROFILE
				c_arrive-=clock();
#endif
							arrive_mail(i);
#ifdef PROFILE
				c_arrive+=clock();
#endif
							go_back(i);
						}else if(node[i].state == BACK){
							node[i].timer = 0;
							node[i].state = HERE;
						}
					}
					/* zBõªo­·é */
					if(node[i].state == HERE){
#ifdef PROFILE
				c_take-=clock();
#endif
						take_mail(i);
#ifdef PROFILE
				c_take+=clock();
#endif
					}
					if(node[i].timer && min>node[i].timer)min=node[i].timer;
				}
#ifdef PROFILE
				c_print-=clock();
#endif
				print_arrive();
#ifdef PROFILE
				c_print+=clock();
#endif
				time=min;
			}
			printf("\n");
#ifdef PROFILE
			c_sim+=clock();
#endif
		}
	}
#ifdef PROFILE
	c_all+=clock();
	printf(
		"init:  %d\n"
		"input: %d\n"
		"sim:   %d\n"
		" mail: %d\n"
		" arriv:%d\n"
		" take: %d\n"
		" print:%d\n"
		"all:   %d\n"
		,c_init, c_input, c_sim, c_mail, c_arrive, c_take, c_print, c_all);
#endif
	return 0;
}

void init_nodes(int n){
	int i,j;
	for(i=0;i<n;i++){
		node[i].state = HERE;
		node[i].timer = 0;
		for(j=0;j<n;j++){
			node[i].dist[j] = MAX_DIST;
			node[i].distf[j] = FALSE;
			node[i].distnext[j] = -1;
		}
		node[i].dist[i] = 0;
		node[i].distf[i] = TRUE;
		node[i].distnext[i] = i;
		node[i].dst = -1;
		node[i].post_queue = NULL;
		node[i].deli_queue = NULL;
	}
}

int check_mail(int l){
	int i,cnt;
	cnt=0;
	for(i=0;i<l;i++){
		if(mail[i].state != DONE)cnt++;
	}
	return cnt;
}

void post_mail(Mail *m){
	add_mail(&(node[m->src].post_queue),m);
	m->state = POST;
}

void take_mail(int n){
	Mail *que,**q,*tmp;

	/* zB·é[ª é©H */
	if(node[n].post_queue!=NULL){

		/* ÅÌ[ðzBXgÖÚ® */
		que = node[n].post_queue;
		del_mail(&(node[n].post_queue),que);
		add_mail(&(node[n].deli_queue),que);

		que->state = DELI;
		node[n].state = GO;
		node[n].timer = time+calc_dist(n,que->dst);/* »Ý{ÚWnÜÅÌ£ */
		node[n].dst = node[n].distnext[que->dst];

		/* ¯¶Í¯æÌ[ðzBXgÖÚ® */
		q = &(node[n].post_queue);
		while(*q != NULL){
			if((*q)->dst == que->dst){
				tmp = *q;
				tmp->state = DELI;
				del_mail(q,tmp);
				add_mail(&(node[n].deli_queue),tmp);
			}else{
				q = &((*q)->next);
			}
		}
	}
}

void arrive_mail(int n){
	Mail *tmp;

	while(node[n].deli_queue != NULL){
		tmp = node[n].deli_queue;
		del_mail(&(node[n].deli_queue),tmp);
		if(tmp->dst==node[n].dst){
			/* ÅIÍ¯æÉ */
			arrive[arrive_cnt] = tmp;
			arrive_cnt++;
			tmp->state = DONE;
		}else{
			/* ³çÉ] */
			add_mail(&(node[node[n].distnext[tmp->dst]].post_queue),tmp);
			tmp->state = POST;
		}
	}

}

void go_back(int n){
	node[n].state = BACK;
	node[n].timer = time + node[n].dist[node[n].dst];
}

void del_mail(Mail **q,Mail *mail){
	while((*q)!=NULL && (*q)!=mail)q = &((*q)->next);
	if((*q)==mail){
		*q = mail->next;
		mail->next = NULL;
	}
}

void add_mail(Mail **q,Mail *mail){
	while((*q)!=NULL)q = &((*q)->next);
	mail->next = NULL;
	*q = mail;
}



int calc_dist(int a, int b){
	static char past[MAX_NODE];/* ßÉÊÁ½m[h */
	static char best[MAX_NODE];/* ÅZÌm[h */
	static int past_n = 0; /* ßÉÊÁ½m[h */
	static int dist = 0;  /* ßÉÊÁÄ«½£ */
	static int bestd = MAX_DISTSUM;  /* ÅZÌ£ */
	int i,j;

	if(past_n==0) bestd = MAX_DISTSUM;/* TõJnú» */

	past[past_n++] = a;

	/* ½Çè¢½Æ« */
	if(a==b){
		/* ¡ñÌoHªÅZÅ êÎÅZoHðXV */
		if(bestd>dist){
			bestd = dist;
			for(i=0;i<past_n;i++)best[i]=past[i];
		}
	}else{
		if(dist<bestd){
			/* êxvZ³êÄ¢é */
			if(node[a].distf[b]==TRUE){
				i = node[a].distnext[b];
				for(j=0;j<past_n;j++)if(past[j]==i)return -1;
				dist += node[a].dist[i];
				calc_dist(i,b);
				dist -= node[a].dist[i];
			}else{
				for(i=0;i<node_num;i++){
					for(j=0;j<past_n;j++)if(past[j]==i)break;
					if(j!=past_n)continue;
					if(MAX_DIST>node[a].dist[i]){
						dist += node[a].dist[i];
						calc_dist(i,b);
						dist -= node[a].dist[i];
					}
				}
			}
		}
	}
	past_n--;

	/* TõI¹Ê½f */
	if(past_n==0){
		for(i=0;best[i]!=b;i++){
			node[best[i]].distnext[b] = best[i+1];
			node[best[i+1]].distnext[a] = best[i];
			node[best[i]].distf[b] = TRUE;
			node[best[i+1]].distf[a] = TRUE;
		}
		return  node[a].dist[node[a].distnext[b]];
	}
	return  0;
}

void print_arrive(void){
	int i;
	if(arrive_cnt > 0){
		qsort(arrive,arrive_cnt,sizeof(Mail*),compare_mail);
		for(i=0;i<arrive_cnt;i++){
			printf("%s %d\n",arrive[i]->label,time);
		}
	}
	arrive_cnt = 0;
}
	

int compare_mail(const void* a, const void* b){
	return strcmp((*(Mail**)a)->label,(*(Mail**)b)->label);
}