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

using namespace std;

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



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

inline void percolate(int K)
{	
	int cheie = D[H[K]];
	int son = 0;
	while(K > 1 && cheie < D[H[son]])
	{
		if(cheie < D[H[son]])
		{
			son = K >> 1;
			swap(H[K], H[son]);
			P[H[K]] = K;
			P[H[son]] = son;
			K = son;
		}
		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 argc, char** argv)
{	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
    int i = 0;
	scanf("%d %d", &N, &M);
	int Nr = N;
	for(i = 1; i <= M; i ++)
	{
		scanf("%d %d %d", &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)
			printf("0 ");
        else printf("%d ", D[i]);
    return 0;
}