#include <cstdio>
#include <vector>

using namespace std;

struct ceva{
int nod,c;
};

int sol[50005],h[50005],nod[50005],temp[50005],size_heap=0,n,m,inf=1000000000;
vector <ceva> v[50005];

void swap(int a,int b)
{
    int tmp=h[b];
    h[b]=h[a];
    h[a]=tmp;
    tmp=nod[h[b]];
    nod[h[b]]=nod[h[a]];
    nod[h[a]]=tmp;
}

void up(int poz)
{
   while(poz!=1)
   {
       if(temp[h[poz]] < temp[h[poz/2]])
       {
           swap(poz,poz/2);
       }
       else
           break;
       poz/=2;
   }
}

void down(int poz)
{
     int dest=poz;

     if(2*poz<=size_heap && temp[h[2*poz]] < temp[h[dest]])//dest=poz
         dest=2*poz;
     if(2*poz+1<=size_heap && temp[h[2*poz+1]] < temp[h[dest]])//dest=(poz?2*poz)
          dest=2*poz+1;

     if(dest!=poz)
      {
          swap(dest,poz);
          down(dest);
      }
}

void adauga(ceva x)
{
    if(temp[x.nod]==0)
    {
     h[++size_heap]=x.nod;
     nod[x.nod]=size_heap;
     temp[x.nod]=x.c;
     up(size_heap);
    }
    else
    {
     if(x.c<temp[x.nod]&&sol[x.nod]==0)
        temp[x.nod]=x.c;
        up(nod[x.nod]);
    }
}

void elim(int poz)
{
     swap(poz, size_heap);
     size_heap--;
     up(poz);
     down(poz);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    int tmp1,tmp2,tmp3,cn;

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&tmp1,&tmp2,&tmp3);
        v[tmp1].push_back({tmp2,tmp3});
    }

    for(int i=0;i<v[1].size();++i)
        adauga(v[1][i]);

    /*for(int i=0;i<=v[1].size();++i)
    {
        h[++size_heap]=v[1][i].c;
        nod[size_heap]=v[1][i].nod;
    }

    for(int i=size_heap/2;i>0;--i)
        down(i);*/      //Ar fi ok si asa?(in loc de for-ul cu adauga())

    cn=n;
    --n;
    while(n)
    {
        sol[h[1]]=temp[h[1]];
        tmp1=h[1];
        tmp2=temp[h[1]];
        elim(1);
        for(int i=0;i<v[tmp1].size();++i)
        {
            v[tmp1][i].c+=tmp2;
            //if(sol[v[tmp1][i].nod]==0)
                adauga(v[tmp1][i]);
        }
        --n;
    }

    for(int i=2;i<=cn;++i)
        printf("%d ",sol[i]);
    printf("\n");

    return 0;
}