#include <stdio.h>
#include <vector>
#define fiu_stang(k) (k<<1)
#define fiu_drept(k) ((k<<1)+1)
#define tata(k) (k>>1)
using namespace std;
const int maxn=50001;
const int inf=1073741824;
int nr, m, s, cost[maxn];
struct rec{
  int ind;
  int cost;
}x;

vector<rec> vecini[maxn];
int drum[maxn],h[maxn],poz[maxn];
int u;

void citire()
{
  int a;
  scanf("%d %d ",&nr,&m);
  for (int i=1;i<=m;i++)
  {
    scanf("%d %d %d ", &a, &x.ind, &x.cost);
    vecini[a].push_back(x);
  }
}

void cerne(int n, int k){
  int fiu,fiud;
  do {
    fiu=0;
    if (fiu_stang(k)<=n){
      fiu = fiu_stang(k);
      fiud=fiu_drept(k);
      if (fiud<=n && drum[h[fiud]]<drum[h[fiu]]){
        fiu=fiud;
      }
      if (drum[h[fiu]]>=drum[h[k]])
        fiu=0;
    }
    if (fiu){
      swap(h[k], h[fiu]);
      poz[h[k]]=k;
      poz[h[fiu]]=fiu;
      k=fiu;
    }
  } while (fiu);
}

void urca(int k){
  int key = h[k],t;
  while ((k>1)&&(drum[key]<drum[h[k>>1]])){
    t=k>>1;
    swap (h[k],h[t]);
    poz[h[k]]=k;
    poz[h[t]]=t;
    k=t;
  }
}

/*void sterge(int &n, int k){
  if (poz[k]){ 
    h[poz[k]]=h[n];
    poz[h[n]]=poz[k];
    int pp=poz[k];
    poz[k]=0;
    n--;
    if ((pp>1)&&(drum[h[pp]]<drum[h[tata(pp)]])){
      urca(pp);
    } else {
      cerne (n,pp);
    }
  //}
} */

void insert(int &n, int y,int unde){
  drum[unde]=y;
  h[++n]=unde;
  poz[unde]=n;
  urca(n);
}

void dijkstra()
{
  int n=0;
  for (int i=2;i<=nr;i++)
    drum[i]=inf;
  int minim;
  register int punct=0;
      insert(n,0,1);
  for (int register i=1;i<=nr;i++)
  {
    minim=drum[h[1]];
    punct=h[1];
//    sterge(n,h[1]);
      poz[h[1]]=0;
      h[1]=h[n];
      poz[h[1]]=1;
      n--;
      cerne(n,1);
    for (vector<rec>::iterator it=vecini[punct].begin();it!=vecini[punct].end();it++){
      int nou=it->cost+minim;
      int indice=it->ind;
      if (drum[indice]>nou)
        if (poz[indice]==0)
          insert(n,nou,indice);
        else{
          drum[indice]=nou;
          urca(poz[indice]);
        }
    }
  }
} 



int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    for (int i=2;i<=nr;i++)
      printf("%d ", drum[i]<inf ? drum[i] : 0);
    printf("\n");
    return 0;
}