/*
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 29, 2010, 12:49 PM
 */
#include <fstream>
#include <iterator>
#define Nmax 50001
#define inf 0x3f3f3f3f

/*
 *
 */
using namespace std;
struct vertex
{
    int y, c;
    vertex* next;
}z, *L[Nmax];
typedef vertex* list;
int N=1;
int v[Nmax], position[Nmax], dist[Nmax];
inline void push( list& f )
{
    list q;
    q=new vertex;
    q->y=z.y;
    q->c=z.c;
    q->next=f;
    f=q;
}
inline void swap( int& x, int& y )
{
    x+=y;
    y=x-y;
    x-=y;
}
void DownHeap( int x )
{
    int son, right_son;
    while( true )
    {
        son=2*x;
        if( son > N )
            return;
        right_son=2*x+1;
        if( right_son <= N && dist[v[son]] > dist[v[right_son]] )
            son=right_son;
        if( dist[v[son]] >= dist[v[x]] )
            return;
        swap( v[x], v[son] );
        swap( position[v[x]], position[v[son]] );
        x=son;
    }
}
void UpHeap( int x )
{
    int key=dist[v[x]], f=x/2;
    while( x > 1 && key < dist[v[f]] )
    {
        swap( v[x], v[f] );
        swap( position[v[x]], position[v[f]] );
        x=f;
        f/=2;
    }
}
int main()
{list p;
 int n, m, x, i, vertex, vertexc;
    ifstream in("dijkstra.in");
    in>>n>>m;
    while( m-- )
    {
        in>>x>>z.y>>z.c;
        push( L[x] );
    }
     for( i=2, x=n; i <= x; ++i, --x )
        position[x]=position[i]=-1;

    v[N]=1;
    position[1]=1;
    while( N )
    {
        swap( position[v[1]], position[v[N]] );
        vertex=v[1];
        vertexc=dist[v[1]];
        v[1]=v[N];
        v[N]=0;
        --N;
        DownHeap( 1 );
        for( p=L[vertex]; p; p=p->next )
        {
            if( -1 == position[p->y] )
            {
                dist[p->y]=vertexc+p->c;
                v[++N]=p->y;
                position[p->y]=N;
                UpHeap( position[p->y] );
                continue;
            }
            if( dist[p->y] > vertexc + p->c )
            {
                 dist[p->y]=vertexc+p->c;
                 UpHeap( position[p->y] );
            }
        }
    }
    ofstream out("dijkstra.out");
    copy( dist+2, dist+n+1, ostream_iterator<int>(out, " ") );
    return 0;
}