//Dijkstra - Varianta cu Heap-uri

#include <fstream>
using namespace std;

const int infinit=10000001;
const int maxn=50005;

struct nod{
       int vf, cost;
       nod *next;  
} *vecini[maxn];

int n,m,k;
int d[maxn],h[maxn],poz[maxn];
inline int left_son(int z)
{
       return z<<1;
}
inline int right_son(int z)
{
       return z<<1+1;
}
inline int father(int z)
{
       return z>>1;
}
void swap(int i, int j)
{
     int t=h[i];
     h[i]=h[j];
     h[j]=t;
}
void add(nod *&prim,int x,int y)
{
     nod *p=new nod;
     p->vf=x;
     p->cost=y;
     p->next=prim;
     prim=p;
}

void upheap(int z)
{
     int dad;
     while(z>1)
     {
      dad=father(z);
      if(d[h[dad]]>d[h[z]])
      {
                              poz[h[z]]=dad;
                              poz[h[dad]]=z;
                              swap(dad,z);
                              z=dad;
      }
      else return;
     }
}

void downheap(int z)
{
     int son;
     while(z<=k)
     {
      son=z;
      if(left_son(z)<=k)
      {
       son=left_son(z);
       if(right_son(z)<=k && d[h[right_son(z)]]<d[h[left_son(z)]])
        son=right_son(z);
      }
      else return;
      if(d[h[z]]>d[h[son]])
      {
       poz[h[z]]=son;
       poz[h[son]]=z;
       swap(son,z);  
       z=son;
      }
      else return;
     }
}

void citire()
{
     int i,x,y,z;
     ifstream f("dijkstra.in");
     f>>n>>m;
     for(i=1;i<=m;i++)
     {
      f>>x>>y>>z;
      add(vecini[x],y,z);
     }
     f.close();
}

void dijkstra()
{
     int i,min;
     for(i=2;i<=n;i++)
      d[i]=infinit, poz[i]=-1;
     poz[1]=1;
     h[++k]=1;
     while(k)
     {
           min=h[1];
           swap(1,k);
           poz[h[1]]=1;
           --k;
           downheap(1);
           nod *p=vecini[min];
           while(p)
           {
                   if(d[p->vf]>d[min]+p->cost)
                    d[p->vf]=d[min]+p->cost;
                   if(poz[p->vf]!=-1)
                    upheap(poz[p->vf]);
                   else
                   {
                       h[++k]=p->vf;
                       poz[h[k]]=k;
                       upheap(k);
                   }
                   p=p->next;
           }
     }
}

void afisare()
{
     ofstream g("dijkstra.out");
     int i;
     for(i=2;i<=n;i++)
      if(d[i]!=infinit)
       g<<d[i]<<" ";
      else
       g<<"0 ";
     g<<"\n";
     g.close(); 
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}