#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 unsigned int inf=0xffffffff;
unsigned int nr, m, s, cost[maxn];
struct rec{
  unsigned int ind;
  unsigned int cost;
}x;

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


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

void cerne(unsigned int n,unsigned 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(unsigned 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 insert(unsigned int &n,unsigned int y,unsigned int unde){
  drum[unde]=y;
  h[++n]=unde;
  poz[unde]=n;
  urca(n);
}

void dijkstra()
{
  unsigned int n=0;
//  for (int i=2;i<=nr;i++)
//    drum[i]=inf;
  memset(&drum[2],-1,4*(nr-1));
  for (int i=0;i<=nr+4;i++)
    printf("%d ",drum[i]);
  unsigned int minim,punct=0;
      insert(n,0,1);
  for (unsigned int register i=1;i<=nr;i++)
  {
    minim=drum[h[1]];
    punct=h[1];
      poz[h[1]]=0;
      h[1]=h[n];
      poz[h[1]]=1;
      n--;
      cerne(n,1);
    for (register vector<rec>::iterator it=vecini[punct].begin();it!=vecini[punct].end();it++){
      unsigned int nou=it->cost+minim;
      unsigned 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 (register unsigned int i=2;i<=nr;i++)
      printf("%d ", drum[i]<inf ? drum[i] : 0);
    printf("\n");
    return 0;
}