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

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
struct Graph
{
    unsigned vertex,value;
    Graph *next;
} **List;

inline void Insert( int x, int y, int c )
{
    Graph *q;
    q=(Graph*)malloc( sizeof(Graph) );
    q->vertex=y; q->value=c;
    q->next=List[x]; List[x]=q;
}
int main()
{unsigned N,M,x,y,c,i,max;
 Graph *p;
    in.open("dijkstra.in");
    in>>N>>M;
    List=(Graph**)malloc((N+1)*sizeof(Graph));
    while( M-- )
    {
        in>>x>>y>>c;
        Insert( x, y, c );
        if( List[x] ) List[x]=(Graph*)realloc( (void*)List[x], sizeof(*List[x])/sizeof(Graph) );
        else List[x]=(Graph*)malloc(sizeof(Graph));
        if( c > max ) max=c;
    }
    ++max;
    vector<unsigned> dist( N+1, max ),Q;
    vector<unsigned>::iterator it,iend,imin;
    dist[1]=0;
    for( i=1; i <= N; ++i ) Q.push_back(i);
    dist[1]=0;
    while( !Q.empty() )
    {
        for( iend=Q.end(), imin=it=Q.begin(); it < iend; ++it )
           if( dist[*imin] > dist[*it] ) imin=it;
        if( 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;
}