/* 
 * 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];
 vector<unsigned> dist,Q;
 vector<unsigned>::iterator it,iend,imin,m,mij;
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;
}
inline vector<unsigned>::iterator minim( vector<unsigned>::iterator a, vector<unsigned>::iterator b )
{
    return dist[*a] < dist[*b] ? a : b;
}
inline vector<unsigned>::iterator search( vector<unsigned>::iterator st, vector<unsigned>::iterator dr )
{
    if( st == dr ) return st;
    else  if( st < dr )
          {
            m=st+(dr-st)/2; mij=m+1;
            return minim( search( st, m ) , search( mij, dr )  );
          }
    return Q.end();
}
int main()
{unsigned N,M,x,y,c,i,max;
 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;
    dist.push_back(max);
    for( i=1; i <= N; ++i ) dist.push_back(max),Q.push_back(i);
    dist[1]=0;
    while( !Q.empty() )
    {
        imin=search( Q.begin(), Q.end() );
        if( Q.end() == imin || 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");
    for( iend=dist.end(), it=dist.begin()+2; it < iend; ++it )
        if( max == *it ) out<<"0 ";
        else out<<*it<<' ';
    return EXIT_SUCCESS; 
}