#include <cstdio>
#include <vector>

using namespace std;

struct ceva{
int nod,c;
};

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

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

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

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

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

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

void adauga(ceva x)
{
     h[++size_heap]=x.c;
     nod[size_heap]=x.nod;
     up(size_heap);
}

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[nod[1]]=h[1];
        tmp1=nod[1];
        tmp2=h[1];
        elim(1);
        for(int i=0;i<v[tmp1].size();++i)
        {
            v[tmp1][i].c+=tmp2;
            adauga(v[tmp1][i]);
        }
        --n;
    }

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

    return 0;
}