#include<stdio.h>
#define maxn 50010
int d[maxn],heap[maxn],poz[maxn],n,m,hp;
int *nr[maxn],*cost[maxn];
char ap[maxn];
void downheap(int ax,int p,int nod){
	int i,a;
	i=1;
	a=2;
	while((ax>d[a] || ax>d[a+1]) && (a<=hp || a+1<=hp)){
		if(a+1<=hp){
			if(d[heap[a]]<d[heap[a+1]]){
				heap[i]=heap[a];
				i=a;
			}
			else{
				heap[i]=heap[a+1];
				i=a+1;
			}
		}
		else{
			heap[i]=heap[a];
			i=a;
		}
		a=i<<1;
	}
	heap[i]=nod;
	poz[nod]=i;
}
void upheap(int ax,int p,int nod){
	int i=p,a;
	a=i>>1;
	while(ax<d[heap[a]] && a>0){
		heap[i]=heap[a];
		i=a;
		a>>=1;
	}
	poz[nod]=i;
	d[nod]=ax;
	heap[i]=nod;
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int a,b,c,i,j;

	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		++d[a];
	}
	fclose(stdin);
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i){
		nr[i]=new int [d[i]+1];
		cost[i]=new int [d[i]+1];
		cost[i][0]=nr[i][0]=0;
		d[i]=0;
	}
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		nr[a][++nr[a][0]]=b;
		cost[a][nr[a][0]]=c;
	}
	hp=0;
	for(i=1;i<=nr[1][0];++i){
		++hp;
		heap[hp]=nr[1][i];
		d[nr[1][i]]=cost[1][i];
		upheap(cost[1][i],hp,nr[1][i]);
		ap[nr[1][i]]=1;
	}
	while(hp){
		poz[heap[1]]=0;
		ap[heap[1]]=0;
		i=heap[1];
		heap[1]=heap[hp];
		heap[hp]=0;
		--hp;
		downheap(d[heap[1]],poz[heap[1]],heap[1]);
		for(j=1;j<=nr[i][0];++j){
			if(ap[nr[i][j]]){
				if(d[i]+cost[i][j]<d[nr[i][j]])
					upheap(d[i]+cost[i][j],poz[nr[i][j]],nr[i][j]);
			}
			else{
				heap[++hp]=nr[i][j];
				d[nr[i][j]]=d[i]+cost[i][j];
				upheap(d[i]+cost[i][j],hp,nr[i][j]);
				ap[nr[i][j]]=1;
			}
		}
	}
	
	printf("%d",d[2]);
	for(i=3;i<=n;++i)
		printf(" %d",d[i]);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}