#include <vector>
#include <algorithm>
#include <fstream>
#include <cstdlib>
#define INF 0x3f3f3f3f

using namespace std;

const int nmax = 50011;
const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
typedef int Heap[nmax];
Heap H;
int P[nmax], D[nmax], N, M, x, y, c, cost;
vector<pair< int, int > > Nod[nmax];

ifstream fin(iname);
ofstream fout(oname);

inline void sift(int K)
{
	for(int son = 2 * K; son < N; son = son * 2, K = son)
	{
		if(D[H[son]] > D[H[son + 1]] && son < N)
			son ++;
		if(D[H[son]] > D[H[K]])
		{
			swap(H[son], H[K]);
			swap(P[H[son]], P[H[K]]);
		}
		else
			return;
	}
}

inline void percolate(int K)
{	
	int cheie = D[H[K]];
	while(K > 1 && cheie < D[H[K/2]])
	{
		if(cheie < D[H[K/2]])
		{
			swap(H[K], H[K/2]);
			swap(P[K], P[K/2]);
			K = K/2;
		}
		else
			break;
	}
}

inline int out(void)
{
	int val = H[1];
	P[H[1]] = 0;
	H[1] = H[N];
	-- N;
	sift(1);
	return val;
}
	
inline void push(int K)
{
    H[++N] = K;
    P[K] = N;
    percolate(N);
}

int main()
{
    int i = 0;
	fin >> N >> M;
	int Nr = N;
	for(i = 1; i <= M; i ++)
	{
		fin >> x >> y >> cost;
		Nod[x].push_back(make_pair(y, cost));
	}
		
    for(i = 2; i <= N; i ++)
		D[i] = INF;
	
    for( N = 0, push(1); N; )
    {	
        x = out();
        for(vector<pair< int, int > >::iterator it = Nod[x].begin(); it != Nod[x].end();  ++it )
        {
            y = it -> first;
			c = it -> second;
            if( D[y] > D[x] + c )
            {
                D[y] = D[x] + c;
                if(!P[y])
                    push(y);
                else percolate(P[y]);
            }
        }
    }
	
    for( i = 2; i <= Nr; i ++)
        if(D[i] == INF)
			fout << "0 ";
        else fout << D[i] << " ";
    return 0;
}