#include <fstream>
#include <vector>
#define INF 999999999
using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct muchie{ int v,cost; };

vector <muchie> ADJ [50005];
vector <muchie> :: iterator it;

int n,p,a,b,c,D[50005],S[50005],m;

void dijkstra( int nod )
{
    int i,pas,v,minim;
    for ( i=1; i<=n; i++ )
    {
        S[i]=0;
        D[i]=INF;
    }
    D[ nod ]=0;
    for ( pas=1; pas<=n; pas++)
    {
        /// se cauta varful v cu S[v]=0 si D[v] minim
        minim=INF;
        v=0;
        for ( i=1; i<=n; i++ )
            if( S[i]==0 && D[i] < minim)
            {
                v=i;
                minim=D[i];
            }
        if (v==0)
            break;
        S[v]=1;
        /// se produc imbunatatiri in D din cauza lui v
        for ( it=ADJ[v].begin(); it!=ADJ[v].end(); it++ )
        {
            i=(*it).v;
            c=(*it).cost;
            D[i]=min( D[i] , D[v] + c );
        }
    }
}

int main()
{
    int i;
    fi>>n>>m;
    for( i=1; i<=m; i++ )
    {
        fi>>a>>b>>c;
        /// se consemneaza arcul (a,b) de pondere c
        muchie mm;
        mm.v=b;
        mm.cost=c;
        ADJ[a].push_back(mm);
    }
    dijkstra( 1 );

    for ( i=2; i<=n; i++)
        if (D[i]==INF)
            fo<<0<<" ";
        else
            fo<<D[i]<<" ";

    fi.close();
    fo.close();
    return 0;
}