#include <fstream>
#define inf 1<<30
#define maxn 50001

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,heap[maxn],poz[maxn],dist[maxn],lung;

struct graf
{
    int nod,cost;
    graf * urm;
};
graf *a[maxn];

void swap(int i,int j)
{
    int aux=heap[i];
    heap[i]=heap[j];
    heap[j]=aux;
}

void urca(int x)
{
    int tata;
    while(x>1)
    {
        tata=x/2;
        if(dist[heap[tata]]>dist[heap[x]])
        {
            poz[heap[x]]=tata;
            poz[heap[tata]]=x;
            swap(tata,x);
            x=tata;
        }
        else x=1;
    }
}

void coboara(int x)
{
    int fiu;
  while(x<=lung)
  {
      fiu=x;
      if(x*2<=lung)
      {
          fiu=x*2;
          if(fiu+1<=lung)
           if(dist[heap[fiu+1]]<dist[heap[fiu]])
            fiu++;
      }
      else return;
      if(dist[heap[x]]>dist[heap[fiu]])
      {
          poz[heap[x]]=fiu;
          poz[heap[fiu]]=x;
          swap(x,fiu);
          x=fiu;
      }
      else return;
  }
}

void dijkstra()
{
    for(int i=2;i<=n;i++)
     {
         dist[i]=inf;
         poz[i]=-1;
     }
     poz[1]=1;
     heap[++lung]=1;
     while(lung)
     {
         int min=heap[1];
         swap(1,lung);
         poz[heap[1]]=1;
         lung--;
         coboara(1);
         graf *q=a[min];
         while(q)
         {
             if(dist[q->nod]>(dist[min]+q->cost))
             {
                 dist[q->nod]=dist[min]+q->cost;
                 if(poz[q->nod]!=-1) urca(poz[q->nod]);
                 else
                 {
                     heap[++lung]=q->nod;
                     poz[heap[lung]]=lung;
                     urca(lung);
                 }
             }
             q=q->urm;
         }
     }
}

void afis()
{
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==inf) g<<"0 ";
        if(dist[i]!=inf) g<<dist[i]<<" ";
    }
    g<<"\n";
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        graf *q;
        q=new graf;
        q->nod=y;
        q->cost=z;
        q->urm=a[x];
        a[x]=q;
    }
    dijkstra();
    afis();
    return 0;
}