/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 30, 2009, 1:28 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;
int main(int argc, char** argv)
{unsigned N,M,x,y,c,max=1,i;
 Graph *p;
    in.open("dijkstra.in");
    in>>N>>M;
    List=(Graph**)malloc( (N+1)*sizeof(Graph) );
    while( M-- )
    {
        in>>x>>y>>c; max+=c;
        if( List[x] ) List[x]=(Graph*)realloc( (void*)List[x], sizeof(*List[x]) );
        else List[x]=(Graph*)malloc( sizeof(Graph) );
        Graph *q=new Graph;
        q->value=c; q->vertex=y;
        q->next=List[x];
        List[x]=q;
    }
    vector<unsigned> dist( N+1, max );
    vector<unsigned>::const_iterator it,iend;
    dist[1]=0;
    for( i=1; i <= N; ++i )
        for( p=List[i]; p; p=p->next )
            if( dist[i]+p->value < dist[p->vertex] )
              dist[p->vertex]=dist[i]+p->value;
    out.open("dijkstra.out");
    for( it=dist.begin()+2,iend=dist.end(); it < iend; ++it )
        if( max != *it ) out<<*it<<' ';
        else out<<"0 ";
    return (EXIT_SUCCESS);
}