/*
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 14, 2009, 2:58 PM
 */
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define Nmax 50001

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
struct Nod
{
    unsigned vertex,value;
    Nod *next;
} *List[Nmax];
typedef vector<unsigned>::iterator iter;
vector<unsigned> dist,Q;
inline void Insert( unsigned x, unsigned y, unsigned c )
{
    Nod *q;
    q=(Nod*)malloc( sizeof(Nod) );
    q->vertex=y; q->value=c;
    q->next=List[x]; List[x]=q;
}
inline iter minim( iter a, iter b  )
{
    return dist[*a] < dist[*b] ? a : b;
}
inline iter binary_search( iter st, iter dr )
{
    if( st == dr ) return st;
    else if( st < dr )
         {
            iter m=st+(dr-st)/2;
            return minim( binary_search( st, m ), binary_search( m+1, dr ) );
         }
    return Q.end();
}
int main()
{unsigned N,M,x,y,c,i,max=0;
 Nod *p;
    in.open("dijkstra.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y>>c;
        Insert( x, y, c );
        if( c > max ) max=c;
    }
    ++max;
    iter it,iend,imin;
    for( i=1; i <= N; ++i ) Q.push_back(i),dist.push_back(max);
    dist.push_back(max);
    dist[1]=0;
    while( !Q.empty() )
    {
        imin=binary_search( Q.begin(), Q.end() );
        if( Q.end() == imin || max == dist[*imin] ) break;
        for( p=List[*imin];  p; p=p->next )
        {
            if( dist[*imin] + p->value < dist[p->vertex] ) dist[p->vertex]=dist[*imin]+p->value;
        }
        Q.erase(imin);
    }
    out.open("dijkstra.out");
    for( iend=dist.end(), it=dist.begin()+2; it < iend; ++it )
        if( max == *it ) out<<"0 ";
        else out<<*it<<' ';
    return EXIT_SUCCESS;
}