/*
    Keep It Simple!
*/
   
#include<stdio.h>
#include<list>
   
#define max 50001
 
using namespace std;
   
int n,m;
long long L[max];
bool viz[max];
int H[max],P[max],k;
   
list< pair<int,int> > G[50001];
   
int min()
{
    int x = 0;
    for(int i=2;i<=n;i++)
        if(!viz[i])
         if(L[i] < L[x]) x = i;
    return x==0 ? 1:x;
}
void swap(int v[],int a,int b)
{
    int aux = v[a];
    v[a] = v[b];
    v[b] = aux;
}
 
void Update(int x)
{
    int sw = 0;
    while(x/2>0 && !sw)
    {
        sw=1;
        if(L[H[x/2]]>L[H[x]])
        {
            sw=0;
            swap(P,H[x/2],H[x]);
            swap(H,x/2,x);
			x/=2;
        }
    }
}
void GoDown(int x)
{
    int sw = 0;
    while( (2*x+1)<=k || (2*x)<=k )
    {
        if ( sw ) break;
        sw = 1;
        if(L[H[2*x+1]] < L[H[x]] && L[H[2*x+1]] < L[H[2*x]]){ x = 2*x+1; sw = 0;}
        else if ( L[H[2*x]] < L[H[x]] ) { x = 2*x; sw = 0; }
         
        if( !sw )
        {
          swap(P,H[x],H[x/2]);
          swap(H,x,x/2);
        }
    }
}
void Delete(int x)
{
    int aux = L[x];
    L[x] = -1;
    Update(P[x]);
    H[1] = H[k--];
    P[H[1]]=1;
    GoDown(1);
    L[x] = aux;
}
void Dijkstra()
{
    int i=1;
    L[1] = 0;
        while(!viz[i])
        {
            for(list< pair<int,int> >::iterator it = G[i].begin(); it!=G[i].end(); it++)
                if(!viz[it->first])
                 if(L[it->first] > ( L[i] + it->second) )
                 {
                     L[it->first] = L[i] + it->second;
                     Update(P[it->first]);
                 }
            viz[i] = 1;
            Delete(i);
            i = H[1];
        }
}
   
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
       
    scanf("%d %d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back( make_pair(y,c) );
    }
        k=n;
    for(int i=0;i<=n;i++) { L[i] = 2000000000; H[i] = i; P[i] = i; }
    Dijkstra();
    for(int i=0;i<=n;i++) if ( L[i] == 2000000000 ) L[i] = 0;
    for(int i=2;i<=n;i++)
        printf("%lld ",L[i]);
}