/*
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 14, 2009, 2:58 PM
 */
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
struct Graph
{
    unsigned vertex, cost ;
    Graph *next;
};
Graph **L;
vector<unsigned> dist,Q;
typedef vector<unsigned>::iterator it;
inline void Insert( int x, int y, int value )
{
    Graph *q;
    q=new Graph;
    q->vertex=y; q->cost=value;
    q->next=L[x];
    L[x]=q;
}
inline it minim( it a, it b )
{
    return dist[*a] < dist[*b] ? a : b;
}
inline it binary_search( it st, it dr )
{
    if( st == dr ) return st;
    else if( st < dr )
         {it m;
             m=st+(dr-st)/2;
             return minim( binary_search( st, m ), binary_search( m+1, dr) );
         }
    return dist.begin();
}
int main()
{unsigned N,M,x,y,value,max=1;
 it imin;
 Graph *p;  
    in.open("dijkstra.in");
    in>>N>>M;
    L=(Graph**)calloc( N+1 , sizeof(Graph) );
    while( M-- )
    {
        in>>x>>y>>value; max+=value;
        if( L[x] ) L[x]=(Graph*)realloc( (void*)L[x], sizeof(*L[x])/sizeof(Graph) );
        else L[x]=(Graph*)malloc(sizeof(Graph));
        Insert( x, y, value );
    }
    dist.push_back(max); 
    for( register unsigned i=1; i <= N; ++i )
    {
         Q.push_back(i);
         dist.push_back(max);
    }
    dist[1]=0;
    while( !Q.empty() )
    {
        imin=binary_search( Q.begin(), Q.end()-1 );
        if( dist.begin() == imin  ) break;
        for( p=L[*imin]; p; p=p->next )
           if( p->vertex != 0 && dist[*imin]+p->cost < dist[p->vertex] )
             dist[p->vertex]=dist[*imin]+p->cost;
        Q.erase(imin);
    }
    out.open("dijkstra.out");
    for( it iter=dist.begin()+2; *iter; ++iter )
        if( max == *iter ) out<<"0 ";
        else out<<*iter<<' ';
    return EXIT_SUCCESS;
}