#include<cstdio>
#include<cstdlib>
#include<vector>
#define inf 1001
#define maxn 50011
#define maxm 250001
using namespace std;
 
 
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");
 
struct muchie
{
       int nod,cost;
};
 
vector<muchie>A[maxm];
int n,m,d[maxn],heap[maxn],poz[maxn],ind=1;
 
void swap(int &a,int &b)
{
     int aux;
     aux=a;
     a=b;
     b=aux;
}
 
void up_heap(int l)
{
     if (l>1)
             if (d[heap[l/2]]>d[heap[l]])
             {
                  swap(heap[l/2],heap[l]);
                  poz[heap[l/2]]=l/2;
                  poz[heap[l]]=l;
                  up_heap(l/2);
                  }
}
 
void down_heap(int l)
{
     int m;
     if (2*l<=ind)
     {
          m=2*l;
          if (m+1<=ind && d[heap[m]]>d[heap[m+1]])
             m=m+1;
          if (d[heap[m]]<d[heap[l]])
          {
              swap(heap[l],heap[m]);
              poz[heap[l]]=l;
              poz[heap[m]]=m;
              down_heap(m);
              }
          }
}         
                   
 
int main()
{
    int a,i,min,nod1,cost1,x;
    muchie b;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b.nod,&b.cost);
        A[a].push_back(b);
        }
    for (i=2;i<=n;i++)
    {
        d[i]=inf;
        poz[i]=-1;
        }
    poz[1]=1;
    heap[1]=1;
    ind++;
    while (ind>0)
    {
          min=heap[1];
          swap(heap[1],heap[ind]);
          poz[heap[1]]=1;
          ind--;
          down_heap(1);
          for (i=0;i<A[min].size();++i)
          {
              nod1=A[min][i].nod;
              cost1=A[min][i].cost;
              if (d[A[min][i].nod]>d[min]+A[min][i].cost)
 	      {
                 d[A[min][i].nod]=d[min]+A[min][i].cost;
              	 x=poz[nod1];
                 if (x!=-1)
                     up_heap(x);
                 else
                 {
                    ind++;
                    heap[ind]=nod1;
                    poz[heap[ind]]=ind;
                    up_heap(ind);
                    }
                  }
              }
          }
    for (i=2;i<=n;i++)
        if (d[i]!=inf)
           fprintf(g,"%d ",d[i]);
        else
            fprintf(g,"%d ",0);
    return 0;
}