#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 50000
#define MAX_M 250000
#define INF 1e9
struct g{int b,cost;};
int m,n,s;
g heap[MAX_N];
int index[MAX_N];
int dist[MAX_N];
vector <g> graph[MAX_N];

inline int parent(int x){return (x-1)/2;}
inline int leftc(int x){return x*2+1;}
inline int rightc(int x){return x*2+2;}

void upHeap(int i){
  if(heap[i].cost<heap[parent(i)].cost){
    swap(heap[i],heap[parent(i)]);
    index[heap[i].b]=i;
    index[heap[parent(i)].b]=parent(i);
    upHeap(parent(i));
  }
}

void downHeap(int i){
  int left=leftc(i),right=rightc(i),smallest=i;

  if(left<s && heap[left].cost<heap[smallest].cost)
    smallest=left;
  if(right<s && heap[right].cost<heap[smallest].cost)
    smallest=right;

  if(smallest!=i){
    swap(heap[i],heap[smallest]);
    index[heap[i].b]=i;
    index[heap[smallest].b]=smallest;
    downHeap(smallest);
  }
}

void insertHeap(int node,int cost){
  heap[s]={node,cost};
  index[node]=s;
  upHeap(s++);

}

void eraseHeap(int node){
  int i=index[node];
  index[node]=-1;
  heap[i]=heap[s-1];
  index[heap[i].b]=i;
  s--;
  downHeap(i);
  upHeap(i);
}

void updateHeap(int node,int cost){
  int i=index[node];
  heap[i].cost=cost;
  upHeap(i);
  downHeap(i);
}

inline bool inHeap(int x){return index[x]!=-1;}
inline g& findHeap(int x){return heap[index[x]];}
inline g& topHeap(){return heap[0];}
inline bool isEmpty(){return s==0;}

void dijkstra(int node){
  int i;
  g top;

  for(i=0;i<n;i++){
    insertHeap(i,i==node?0:INF);
  }

  while(!isEmpty()){
    top=topHeap();
    eraseHeap(top.b);
    dist[top.b]=top.cost;
    for(g e:graph[top.b]){
      if(inHeap(e.b) && findHeap(e.b).cost>top.cost+e.cost)
        updateHeap(e.b,top.cost+e.cost);
    }
  }
}


int main(){
  FILE *fin,*fout;
  int i,a,b,c;
  fin=fopen("dijkstra.in","r");
  fout=fopen("dijkstra.out","w");
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&a,&b,&c);
    a--,b--;
    graph[a].push_back({b,c});
    //graph[b].push_back({a,c});
  }
  dijkstra(0);

  for(i=1;i<n;i++)
    fprintf(fout,"%d ",dist[i]!=INF?dist[i]:0);

  fclose(fin);
  fclose(fout);
  return 0;
}