/* 
 * 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;
}
int main()
{int N,M,x,y,c,max=-1,i;
 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;
    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");
    copy( dist.begin()+2, dist.end(), ostream_iterator<unsigned>(out," ") );
    return EXIT_SUCCESS; 
}