#include <iostream>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 50001

struct point { int v,c; point *l; } *G[MAXN];
int D[MAXN],n;

struct Comp
{
    bool operator () (const int &a, const int &b)
    {
        return D[a]>D[b];
    }
};

priority_queue<int, vector<int>, Comp> Q;

void read_data ()
{
    int m,x,y,c; point *p;
    freopen ( "dijkstra.in" , "r" , stdin );
    scanf ( "%d %d" , &n , &m );
    while(m--)
    {
        scanf ( "%d %d %d" , &x , &y , &c );
        p=new point; *p = (point) { y,c,G[x] }; G[x]=p;
    }
    fclose ( stdin );
}

int numar ( int x ) { return (x!=INF)?(x):(0); }
void write_data ()
{
    freopen ( "dijkstra.out" , "w" , stdout );
    for ( int i=2 ; i<n ; i++ ) printf ( "%d " , numar(D[i]) );
    printf ( "%d\n" , numar(D[n]) );
    fclose ( stdout );
}

void dijkstra ( int s )
{
    int v;
    memset ( D , INF , (n+1)*sizeof ( int ) ); D[s]=0;
    D[s]=0;
    Q.push(s);
    while (!Q.empty())
    {
        v = Q.top(); Q.pop();
        for ( point *p=G[v] ; p ; p=p->l )
            if (D[p->v]>D[v]+p->c)
            {
                D[p->v]=D[v]+p->c;
                Q.push(p->v);
            }
    }
}

int main ()
{
    read_data ();
    dijkstra(1);
    write_data ();
    return 0;
}