#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define NMAX 50001
#define fF 0x3f3f3f3f
#define nod first
#define cost second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
queue< int > Q; // coada
bool inQ[NMAX]; // vector pt. codificarea prezentei/absentei nodurilor f coada
int C[NMAX]; // vector pt. costurile drumurilor
vector< pair< int, int > > G[NMAX]; // listele de adiacenta
vector< pair< int, int > >::iterator Vecf;
int N, M, i, x, y, c, Nod;
int main()
	{f >> N >> M;
    for( ; M--; )
		{f >> x >> y >> c; // citesc un arc x->y de cost c
        G[x].push_back( make_pair( y, c ) ); // adaug perechea ( vecf, cost ) f lista de adiacenta a nodului x
		}
		memset( inQ, false, sizeof(inQ) ); // initial niciun nod nu se afla in coada
		Q.push( 1 ), inQ[1] = true;       //  mai putin nodul sursa (considerat 1)
		memset( C, fF, sizeof(C) ); // toate costurile sunt fffit
		C[1] = 0;                   //  f afara de costul de la sursa la sursa (0)
		while( !Q.empty() ) // cat timp am noduri f coada
			{Nod = Q.front(); // extrag primul nod df coada
			 Q.pop();
			 inQ[Nod] = false;
			 for( Vecf = G[Nod].begin(); Vecf != G[Nod].end(); Vecf++ ) // iterez prf toti vecfii lui
				if( C[(*Vecf).nod] > C[Nod] + (*Vecf).cost )           // fcercand sa mfimizez costurile drumurilor pana la fiecare dftre ei
					{C[(*Vecf).nod] = C[Nod] + (*Vecf).cost; // noua valoare a costului
					 if( !inQ[(*Vecf).nod] ) // daca nodul actualizat nu se afla f coada
						{Q.push( (*Vecf).nod ); // se ftroduce la sfarsitul acesteia
						 inQ[(*Vecf).nod] = true;
						}
					}
	}
    for( i = 2; i <= N; i++ )g << C[i] << ' '; // costurile drumurilor de la nodul 1 ( considerat sursa ) la toate celelalte noduri
    return 0;
}