/* 
 * 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];

inline void Insert( int x, int y, int c )
{
    Nod *q;
    q=(Nod*)malloc( sizeof(Nod) );
    q->vertex=y; q->value=c;
    q->next=List[x]; List[x]=q;
}
unsigned max1;
inline void output( unsigned it )
{
    if( max1 == it ) out<<"0 ";
    else out<<it<<' ';
}
int main()
{unsigned N,M,x,y,c,i;
 Nod *p;
    in.open("dijkstra.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y>>c;
        Insert( x, y, c );
        if( c > max1 ) max1=c;
    }
    ++max1;
    vector<unsigned> dist( N+1, max1 ),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( max1 == 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_each( dist.begin()+2, dist.end(), output );
    return EXIT_SUCCESS; 
}