#include<fstream>
#include<vector>
#include<queue>
#include<cstdio>
#define pai pair<int,int>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMAX = 50005;
const int INF  = (1<<30);

int N,M,dj[NMAX+1];

vector<pai> v[NMAX+1];

priority_queue< pai, vector<pai>, greater<pai> > heap;

int next_int()
{
    char c;
    int nr= 0;
    in.get(c);
    while( c>47 && c<59 )
    {
        nr= nr*10+c-48;
        in.get(c);
    }
    return nr;
}

int main()
{
    in >> N >> M;   in.get();
	for( int i=1;  i<=M;  ++i ) {
	    int x,y,c;
	    x= next_int();
	    y= next_int();
	    c= next_int();
	    v[ x ].push_back( make_pair( y , c ) );
	}

	for( int i= 2;  i<=N;  ++i )
        dj[i] = INF;

	heap.push( make_pair( 0 , 1 ) );

	while( !heap.empty() ) {
        int x;
	    x= heap.top().second;
	    heap.pop();
	    for( vector<pai>::iterator it= v[x].begin();   it != v[x].end();   ++it ) {
            if( dj[ x ] + it->second < dj[ it->first ] ) {
                dj[ it->first ]= dj[x] + it->second;
                heap.push( make_pair( dj[ it->first ] , it->first ) );
            }
        }
	}

	for( int i= 2; i<=N; ++i ) {
        if( dj[i] == INF ) out << "0 ";
        else out << dj[i] << ' ';
    }

	return 0;
}