#include<cstdio>
#include<cstdlib>
#include<vector>
#define inf 1000000000
#define MAXN 50002
#define MAXM 250002
using namespace std;
struct muchie{
       int nod;
       int cost;
       };
vector<muchie> mch[MAXN];
int n,m;
int a[MAXN],b[MAXM],v[MAXN];
int minim(int x,int y)
{
       if(x<y)
       return x;
       return y;
}
void update(int nod,int st,int dr,int index,int cost)
{
     if(st==dr)
     {
               b[nod]=cost;
               return;
     }
     else
     {
         int mij=(st+dr)/2;
         if(index<=mij) update(nod*2,st,mij,index,cost);
         else update(nod*2+1,mij+1,dr,index,cost);
         b[nod]=minim(b[nod*2],b[nod*2+1]);
     }
}
void solve(int nod,int st,int dr)
{
     if(st==dr)
     {
               if(st==1)
                        b[nod]=0;
               else
                        b[nod]=inf;
               a[st]=inf;
     }
     else
     {
         int mij=(st+dr)/2;
         solve(nod*2,st,mij);
         solve(nod*2+1,mij+1,dr);
         b[nod]=minim(b[nod*2],b[nod*2+1]);
     }
}
int cost_minim(int nod,int st,int dr)
{
    if(st==dr)
              return st;
    else
    {
         int mij=(st+dr)/2;
         if(minim(b[nod*2],b[nod*2+1])==b[nod*2])
              return cost_minim(nod*2,st,mij);
         else
              return cost_minim(nod*2+1,mij+1,dr);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);    
    int i,x,p;
    muchie y;
    scanf("%d",&n); //nr de noduri
    scanf("%d",&m); //nr de muchii
    for(i=1;i<=m;i++)
    {
                     scanf("%d%d%d",&x,&y.nod,&y.cost);
                     mch[x].push_back(y);
    }
    solve(1,1,n);
    while(b[1]!=inf)
    {
                    p=cost_minim(1,1,n);
                    a[p]=b[1];
                    v[p]=1;
                    for(i=0;i<mch[p].size();i++)
                    {
                           if(!v[mch[p][i].nod] && a[p]+mch[p][i].cost<a[mch[p][i].nod])
                           {
                                      a[mch[p][i].nod]=a[p]+mch[p][i].cost;
                                      update(1,1,n,mch[p][i].nod,a[mch[p][i].nod]);
                           }
                    }
                    update(1,1,n,p,inf);
    }
    for(i=2;i<=n;i++)
    {
                     if(a[i]!=inf)
                                  printf("%d ",a[i]);
                     else
                                  printf("0 ");
    }
                     
    
    return 0;
}