/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 21, 2009, 1:56 PM
 */
#include <queue>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define INF 1<<30
#define Nmax 51000
/*
 * 
 */

using namespace std;
ifstream in;
ofstream out;
struct Nod
{
    int vertex,cost;
    Nod *next;
};
Nod *List[Nmax];
inline void Insert( int x, int y, int c )
{
    Nod *q;
    q=(Nod*)malloc( sizeof(Nod) );
    q->vertex=y; q->cost=c;
    q->next=List[x];
    List[x]=q;
}
queue<int> Q;
int main(int argc, char** argv)
{int N,M,x,y,c;
 Nod *p;
    in.open("dijkstra.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y>>c;
        Insert( x, y, c );
    }
    vector<int> dist( N, 0 );
    Q.push(1);
    while( !Q.empty() )
    {
        x=Q.front(); Q.pop();
        for( p=List[x]; p; p=p->next )
            if( !dist[p->vertex-1] || p->cost+dist[x-1] < dist[p->vertex-1] )
            {
                dist[p->vertex-1]=p->cost+dist[x-1];
            }
    }
    out.open("dijkstra.out");
    dist[0]=0;
    copy( dist.begin()+1, dist.end(), ostream_iterator<int>(out," ") );
    free(*List);
    return (EXIT_SUCCESS);
}