#include<stdio.h>
#define maxn 50010
int d[maxn],heap[maxn],poz[maxn],n,m,hp,fol[maxn];
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;
ap[1]=1;
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];
fol[i]=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(!fol[nr[i][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;
}