#include <stdio.h>
#include <stdlib.h>
#define N 50010
#define INF 1000000
int *cine[N],*cost[N],dist[N],n,m,cati[N];
struct nod{
	int who,cost;
};
struct nod coada[1000000];
void scan(){
	int i,j,c;
	freopen("dijsktra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    while (m--){
      scanf("%d%d%d",&i,&j,&c);
      ++cati[i];
    }
	fclose(stdin);
    for (i=1;i<=n;++i){
       dist[i]=INF;
       cine[n]=(int*)malloc(cati[i]+5);
       cost[n]=(int*)malloc(cati[i]+5);
       cati[i]=0;
    }
    freopen("dijsktra.in","r",stdin);
    scanf("%d%d",&n,&m);
    while (m--){
      scanf("%d%d%d",&i,&j,&c);
      ++cati[i];
      cine[i][cati[i]]=j;
      cost[i][cati[i]]=c;
    }
}
void bellman_ford(){
    int p,u,i;
	struct nod now,e;
    p=u=1;
    coada[u++]=(struct nod){1,0};
    while (p<u){			// cat timp coada nu e vida
		e=coada[p++];		// scot primul element din coada
        for (i=1;i<=cati[e.who];++i){
           if (dist[ cine[e.who][i] ] > e.cost + cost [e.who][cine[e.who][i] ]){
               dist[ cine[e.who][i] ] = e.cost + cost [e.who][cine[e.who][i] ];
           	   coada[u++]=(struct nod){cine[e.who][i],dist[ cine[e.who][i] ]};
		   }
        }
    }
}
void print(){
    int i;
    for (i=2;i<=n;++i)
       printf("%d ",dist[i]);
	fclose(stdin);
	fclose(stdout);
    exit(0);
}
int main(){
	scan();
    bellman_ford();
    print();
}