#include <stdio.h>
#include <stdlib.h>
#define N 50010
#define INF 250000010
int *cine[N],*cost[N],dist[N],n,m,cati[N];
struct nod{
	int cine,cost;
};
struct nod coada[500000];
int incoada[N];
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(){
    register int p,u,i;
    struct nod now,e;
    p=u=0;
    coada[u++]=(struct nod){1,0};
    while (p<u){			// cat timp coada nu e vida
	e=coada[p++];		// scot primul element din coada
        incoada[e.cine]=0;
	//printf("(%d %d) ",e.cine,e.cost);
        for (i=1;i<=cati[e.cine];++i){
            now.cine=cine[e.cine][i];
            now.cost=cost[e.cine][i];
            if (dist[ now.cine] > e.cost + now.cost){
               dist[ now.cine] = e.cost + now.cost;
               if (!incoada[now.cine]){
                 incoada[now.cine]=1;
                 coada[u++]=(struct nod){now.cine,dist[ now.cine]};
               }
            }
        }
    }
}
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();
}