#include <fstream.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;
};
int incoada[N];
int coada[500000];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
void scan(){
    int i,j,c;
    in>>n>>m;
    while (m--){
      in>>i>>j>>c;
      ++cati[i];
    }
    in.close();
	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;
    }
    ifstream in("dijkstra.in");
	in>>n>>m;
	while (m--){
      in>>i>>j>>c;
      ++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();
}