#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;
  key[x]=0;
  q.push({1,0});
  while(!q.empty()){
    edge f=q.top();
    q.pop();
    for(auto i: l[f.y])
      if(key[i.y]>key[f.y]+i.cost){
        key[i.y]=key[f.y]+i.cost;
        q.push({i.y,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++)
    fprintf(fout,"%d ",key[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}