#include <stdio.h>
#include <vector>
#include <queue>
#define INF 2000000000
#define MAXN 50001
FILE *fin,*fout;
int n,key[MAXN];

struct edge{
  int y,cost;
};

struct comp{
  bool operator()(const edge &a, const edge &b){
    return a.cost>b.cost;
  }
};

std::vector<edge>l[MAXN];

void dijkstra(int x){//pornind din nodul x
  for(int i=1; i<=n; i++)
    key[i]=INF;
  std::priority_queue<edge,std::vector<edge>,comp>q;
  q.push({x,0});
  while(!q.empty()){
    edge f=q.top();
    q.pop();
    if(key[f.y]==INF){
      key[f.y]=f.cost;
      for(auto i: l[f.y])
        if(key[i.y]==INF)
          q.push({i.y,f.cost+i.cost});
    }
  }
}

int main(){
  fin=fopen("dijkstra.in","r");
  fout=fopen("dijkstra.out","w");
  int m,cost,i,x,y;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d%d",&x,&y,&cost);
    l[x].push_back({y,cost});
  }
  dijkstra(1);
  for(i=2; i<=n; i++)
    if(key[i]==INF)
      fprintf(fout,"0 ");
    else
      fprintf(fout,"%d ",key[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}