#include<stdio.h>

int k,n,m,*heap,*poz,*drum;
const int infinit=1<<30;

struct nod
{int info;
int cost;
nod *nod_urmator;};

nod *Sfarsit,**ListaFii;

void adauga(int a,int b,int COST)
{nod *aux=new nod;
aux->info=b;
aux->cost=COST;
aux->nod_urmator=ListaFii[a];
ListaFii[a]=aux;}

void initializare()
{
FILE *pin=fopen("dijkstra.in","r");
fscanf(pin,"%d",&n);
fscanf(pin,"%d",&m);

heap=new int[n+1];
drum=new int[n+1];
poz=new int[n+1];
ListaFii=new nod*[n+1];
Sfarsit=new nod;

for(int i=1;i<=n;i++)
  ListaFii[i]=Sfarsit;
  
int a,b,cost;
for(int i=1;i<=m;i++)
  {fscanf(pin,"%d",&a);
  fscanf(pin,"%d",&b);
  fscanf(pin,"%d",&cost);
  adauga(a,b,cost);}

fclose(pin);
}

void inter(int a,int b)
{
int aux=heap[a];
heap[a]=heap[b];
heap[b]=aux;
}

void JosHeap()
{
int tata=1;
while(tata<=k)
  {
  int fiu;
  
  if((tata<<1)>k)
    break;

  fiu=tata<<1;
  if(fiu<k)
    if(drum[heap[fiu]]>drum[heap[fiu+1]])
      fiu=fiu+1;

  if(drum[heap[fiu]]>=drum[heap[tata]])
    break;
  else
    {
    poz[heap[fiu]]=tata;
    poz[heap[tata]]=fiu;
    inter(fiu,tata);
    tata=fiu;
    }
  }
}

void SusHeap(int care)
{
int tata;
while(care>=1)
  {
   if((tata=care>>1)<1) break;
   if(drum[heap[tata]]<drum[heap[care]])
     break;
   else
     {
     poz[heap[care]]=tata;
     poz[heap[tata]]=care;
     inter(tata,care);
     care=tata;
     }
  }
}

inline void init()
{
for(int i=2;i<=n;i++)
  {poz[i]=-1;
  drum[i]=infinit;
  }
poz[1]=1;
drum[1]=0;
heap[++k]=1;
}

void dijkstra()
{
init();
int min;
while(k)
  {
  min=heap[1];
  inter(1,k);
  k--;
  poz[heap[1]]=1;
  JosHeap();
  for(nod *aux=ListaFii[min];aux!=Sfarsit;aux=aux->nod_urmator)
    {
    if(drum[aux->info]>drum[min]+aux->cost)
      {
      drum[aux->info]=drum[min]+aux->cost;
      if(poz[aux->info]!=-1)
        SusHeap(poz[aux->info]);
      else
        {
        heap[++k]=aux->info;
        poz[aux->info]=k;
        SusHeap(k);
        }
      }
    }
  }
}

void rezolva()
{dijkstra();}

void incheie()
{
FILE *pout=fopen("dijkstra.out","w");
for(int i=2;i<=n;i++)
  if(drum[i]!=infinit)
    fprintf(pout,"%d ",drum[i]);
  else
    fprintf(pout,"%d ",0);
fclose(pout);
}

int main()
{initializare();
rezolva();
incheie();}