#include <vector>
#define fiu_stang(k) (k<<1)
#define fiu_drept(k) ((k<<1)+1)
#define tata(k) (k>>1)
#include <cstdio>
#define DIM 8192
char ax[DIM+16];
int pz;
inline void cit(int &x)
{
            x=0;
            while(ax[pz]<'0' || ax[pz]>'9')
                        if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
            }
}
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);
  cit(nr);
  cit(m);
  for (int i=1;i<=m;i++)
  {
//    scanf("%d %d %d ", &a, &x.ind, &x.cost);
    cit(a);
    cit(x.ind);
    cit(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 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;
  int punct=0;
      insert(n,0,1);
  for (int register i=1;i<=nr;i++)
//  while (n>0)
  {
    minim=drum[h[1]];
    punct=h[1];
//    sterge(n,h[1]);
//      poz[h[1]]=0;
      h[1]=h[n];
      poz[h[1]]=1;
      n--;
      if (drum[h[1]]==inf) break;
      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]);
        }
    }
//    if (n==0) return;
  }
} 



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