/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 30, 2009, 1:28 PM
 */

#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <algorithm>

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;

struct Graph
{
    unsigned vertex, cost;
    Graph *next;
} **L;
inline void Insert( int x, int y, int c )
{
    Graph *q=new Graph;
    q->vertex=y; q->cost=c;
    q->next=L[x];
    L[x]=q;
}
int main()
{unsigned N,M,x,y,c,max=1;
 Graph *p;
    in.open("dijkstra.in");
    in>>N>>M;
    L=(Graph**)malloc( (N+1)*sizeof(Graph) );
    while( M-- )
    {
        in>>x>>y>>c; max+=c;
        if( !L[x] ) L[x]=(Graph*)malloc( sizeof(Graph) );
        else L[x]=(Graph*)realloc( (void*)L[x], sizeof(L[x]) );
        Insert( x, y, c );
    }
    queue< unsigned > Q;
    vector< unsigned > dist( N, max );
    vector< bool > used( N, true );
    Q.push(1); dist[0]=0;
    while( !Q.empty() )
    {
        x=Q.front(); Q.pop();
        used[x-1]=true;
        for( p=L[x]; p && p->vertex ; p=p->next )
            if( dist[x-1]+p->cost < dist[p->vertex-1] )
            {
                dist[p->vertex-1]=dist[x-1]+p->cost;
                if( true == used[p->vertex-1] )
                {Q.push(p->vertex);
                    used[p->vertex-1]=false;
                }
            }
    }
    out.open("dijkstra.out");
    vector< unsigned >::const_iterator it=dist.begin(), iend=dist.end()-1;
    while( it < iend )
    {++it;
        if( max == *it ) out<<"0 ";
        else out<<*it<<' ';
    }
    free(L);
    return EXIT_SUCCESS;
}