#include <stdio.h>
#include <deque>
#include <vector>
#define fiu_stang(k) (k*2)
#define fiu_drept(k) (k*2+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{
  short ind;
  short cost;
}x;

deque<int> coada; 
//vector<rec> vecini[maxn];
int drum[maxn],h[maxn],poz[maxn];
rec vecini[maxn][10700];
int u;

/*inline int tata(int nod){
  return nod>>1;
}

inline int fiu_drept(int nod){
  return nod*2+1;
}

inline int fiu_stang(int nod){
  return nod*2;
}
*/
/*void afis_poz(int nr){
  cout<<"pozt ";
  for (int i=1; i<=nr;i++)
    cout<<poz[i]<<" ";
  cout<<endl;
}

void afis_heap(int n){
  cout<<"heap ";
  for (int i=1; i<=n;i++)
    cout<<drum[h[i]]<<" ";
  cout<<endl;
}

void afis_drum(int nr){
  cout<<"drum ";
  for (int i=1; i<=nr;i++)
    cout<<drum[i]<<" ";
  cout<<endl<<"************"<<endl;
}*/

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

void cerne(int n, int k){
  int fiu;
  do {
    fiu=0;
    if (fiu_stang(k)<=n){
      fiu = fiu_stang(k);
      if (fiu_drept(k)<=n && drum[h[fiu_drept(k)]]<drum[h[fiu_stang(k)]]){
        fiu=fiu_drept(k);
      }
      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/2]])){
    t=k/2;
    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,punct=0;
      insert(n,0,1);
  for (int i=1;i<=nr;i++)
  {
    minim=drum[h[1]];
    punct=h[1];
    sterge(n,h[1]);
    for (int it=1;it<=vecini[punct][0].ind;it++)
      if (drum[vecini[punct][it].ind]>vecini[punct][it].cost+minim)
        if (poz[vecini[punct][it].ind]==0)
          insert(n,vecini[punct][it].cost+minim,vecini[punct][it].ind);
        else{
          drum[vecini[punct][it].ind]=vecini[punct][it].cost+minim;
          urca(vecini[punct][it].ind);
        }
     
  }
} 



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;
}