#include <stdlib.h>
#include <stdio.h>
#define N 50010
#define INF 250000010
int *cine[N],*cost[N],dist[N],n,m,cati[N];
struct nod{
	int cine,cost;
};
int incoada[N];
int coada[500000];
void scan(){
    int i,j,c,aux,nr;
    char s[23];
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
	int v[5];
	gets(s);
	aux=0;
	nr=0;
	for(i=0;s[i];++i)
		if(s[i]==' '){
			n=aux;
			aux=0;
		}
		else
			aux=aux*10+s[i]-'0';
	m=aux;
    while (m--){
      gets(s);
	  aux=0;nr=0;
	  for (i=0;s[i];++i){
		if (s[i]==' '){
			v[++nr]=aux;
			aux=0;
		}
		else
			aux=aux*10+s[i]-'0';
	  }
	  i=v[1];
      ++cati[i];
    }
    fclose(stdin);
	for (i=1;i<=n;++i){
       dist[i]=INF;
       cine[i]=(int*)malloc(cati[i]*sizeof(int));
       cost[i]=(int*)malloc(cati[i]*sizeof(int));
       cati[i]=0;
    }
    freopen("dijkstra.in","r",stdin);
    gets(s);
    aux=0;
	nr=0;
	for(i=0;s[i];++i)
		if(s[i]==' '){
			n=aux;
			aux=0;
		}
		else
			aux=aux*10+s[i]-'0';
	m=aux;
	while (m--){
      gets(s);
      aux=0;nr=0;
	  for (i=0;s[i];++i){
		if (s[i]==' '){
			v[++nr]=aux;
			aux=0;
		}
		else
			aux=aux*10+s[i]-'0';
	  }
	  i=v[1];
	  j=v[2];
	  c=aux;
	  ++cati[i];
      cine[i][cati[i]]=j;
      cost[i][cati[i]]=c;
    }
}
void bellman_ford(){
	int p,u,i;
    int e,now;
    p=u=0;
    coada[u++]=1;
    dist[1]=0;
    while ((p^u)!=0){
      e=coada[p++];
      incoada[e]=0;
      for (i=1;i<=cati[e];++i){
         now=cine[e][i];
         if(dist[now] > dist[e] + cost[e][i]){
            dist[now] = dist[e] + cost[e][i];
            if (!incoada[now]){
              incoada[now]=1;
              coada[u++]=now;
            }
         }
      }
    }
}
void print(){
    int i,j;
    for (i=2;i<=n;++i){
        if (dist[i]==INF)
           dist[i]=0;
        printf("%d ",dist[i]);
    }
    fclose(stdin);
    fclose(stdout);
    exit(0);
}
int main(){
    scan();
    bellman_ford();
    print();
}