/* 
 * 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 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] );
        position[v[x]]=x;
        position[v[son]]=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] );
        position[v[x]]=x;
        position[v[f]]=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-- )
    {
        list q;
        q=new ::vertex;
        in>>x>>q->y>>q->c;
        q->next=L[x];
        L[x]=q;
    }
    for( i=2, x=n; i <= x; ++i, --x )
        position[x]=position[i]=-1;
    v[N]=1;
    position[1]=1;
    while( N )
    {
        vertex=v[1];
        vertexc=dist[v[1]];
        position[v[1]]=position[v[N]];
        v[1]=v[N];
        --N;
        if( !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;
}