#include <stdio.h>
#include <deque>
using namespace std;
FILE *in,*out;

int n,m;
int start[50002],t[3][250002],d[50002];
bool been[50002];
deque <int> deq;

void read(){
  int x;
  fscanf(in,"%d %d",&n,&m);
  for(int i=1;i<=m;i++){
    fscanf(in,"%d %d %d",&x,&t[0][i],&t[2][i]);
    t[1][i]=start[x];
    start[x]=i;
  }
  for(int i=2;i<=n;i++)
    d[i]=999999999;
}

void bellman_ford(){
  deq.push_back(1);
  while(!deq.empty()){
    int nod=deq.front();
    been[nod]=0;
    int poz=start[nod];
    while(poz){
      int vec=t[0][poz];
      if(d[nod]+t[2][poz]<d[vec]){
        d[vec]=d[nod]+t[2][poz];
        if(!been[vec]){
          been[vec]=1;
          deq.push_back(vec);
        }
      }
      poz=t[1][poz];
    }
    deq.pop_front();
  }
}

void write(){
  for(int i=2;i<=n;i++){
    if(d[i]!=999999999)
      fprintf(out,"%d ",d[i]);
    else fprintf(out,"0 ");
  }
}

int main(){
    in=fopen("dijkstra.in","r");
    out=fopen("dijkstra.out","w");

    read();

    bellman_ford();

    write();

    return 0;
}