#include <fstream.h>
#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];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
void scan(){
    int i,j,c,aux,nr;
    char s[50];
	int v[5];
	//in>>n>>m;
	in.getline(s,50);
	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--){
      in.getline(s,50);
	  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];
    }
    in.close();
	for (i=1;i<=n;++i){
       dist[i]=INF;
       cine[i]=new int[cati[i]+1];
       cost[i]=new int[cati[i]+1];
       cati[i]=0;
    }
    ifstream in("dijkstra.in");
	//in>>n>>m;
	in.getline(s,50);
	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--){
      in.getline(s,50);
	  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(){
    register int p,u,i;
    int e,now;
    p=u=0;
    coada[u++]=1;
    dist[1]=0;
    while (p<u){
      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;
        out<<dist[i]<<" ";
    }
    fclose(stdin);
    fclose(stdout);
    exit(0);
}
int main(){
    scan();
    bellman_ford();
    print();
}