#include <stdio.h>
#include <stdlib.h>
#define N 50010
#define INF 500000
int *cine[N],*cost[N],dist[N],n,m,cati[N];
struct nod{
	int cine,cost;
};
struct nod coada[1000000];
void scan(){
	int i,j,c;
	freopen("dijkstra.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[i]=(int*)malloc(cati[i]+5);
       cost[i]=(int*)malloc(cati[i]+5);
       cati[i]=0;
    }
    freopen("dijkstra.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
		//printf("(%d %d) ",e.cine,e.cost);
        for (i=1;i<=cati[e.cine];++i){
           if (dist[ cine[e.cine][i] ] > e.cost + cost [e.cine][i]){
               dist[ cine[e.cine][i] ] = e.cost + cost [e.cine][i];
           	   coada[u++]=(struct nod){cine[e.cine][i],dist[ cine[e.cine][i] ]};
		   }
        }
    }
}
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();
}