//Include
#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

//Definitii
#define cost first
#define to second

//Constante
const int MAX_SIZE = 50001;
const int oo = (int)2e9;

//Functie de afisare
//inline void afisare();

//Variabile
FILE *in, *out;

int nrNoduri, nrMuchii;

vector<pair<int, int> > graf[MAX_SIZE];
vector<pair<int, int> >::iterator it, end;
vector<int> inQueue, dist;
vector<bool> isInQueue;
queue<int> q;

//Main
int main()
{
	in = fopen("bellmanford.in","rt");
	out = fopen("bellmanford.out","wt");
	fscanf(in, "%d%d", &nrNoduri, &nrMuchii);
	inQueue.resize(nrNoduri+1);
	isInQueue.resize(nrNoduri+1);
	dist.assign(nrNoduri+1, oo);
	
	int cFrom, cTo, cCost;
	for(int i=1 ; i<=nrMuchii ; ++i)
	{
		fscanf(in, "%d%d%d", &cFrom, &cTo, &cCost);
		graf[cFrom].push_back(make_pair(cCost, cTo));
	}
	
	//afisare();
	
	dist[1] = 0;
	inQueue[1] = 1;
	q.push(1);
	
	while(!q.empty())
	{
		int curent = q.front();
		q.pop();
		isInQueue[curent] = false;
		//afisare();
		if(inQueue[curent] > nrNoduri)
		{
			fprintf(out, "Ciclu negativ!");
			fclose(in);
			fclose(out);
			return 0;
		}
		//afisare();
		end = graf[curent].end();
		for(it=graf[curent].begin() ; it!=end ; ++it)
		{
			//afisare();
			if(dist[it->to] > dist[curent] + it->cost)
			{
				dist[it->to] = dist[curent] + it->cost;
				if(!isInQueue[it->to])
				{
					q.push(it->to);
					++inQueue[it->to];
					isInQueue[it->to] = true;
				}
			}
			//afisare();
		}
	}
	//afisare();
	for(int i=2 ; i<= nrNoduri ; ++i)
		fprintf(out, "%d ", dist[i]);
	
	fclose(in);
	fclose(out);
	return 0;
}

/*inline void afisare()
{
	system("cls");
	printf("Graf:");
	for(int i=1 ; i<=nrNoduri ; ++i)
	{
		printf("\n%d:", i);
		for(vector<pair<int, int> >::iterator it=graf[i].begin() ; it!=graf[i].end() ; ++it)
			printf(" (%d, %d)", it->to, it->cost);
	}
	
	printf("\n\n\n\nDistanta:\n");
	for(int i=1 ; i<=nrNoduri ; ++i)
		printf("%d ", dist[i]);
	
	printf("\n\n\n\nisInQueue:\n");
	for(int i=1 ; i<=nrNoduri ; ++i)
		printf("%d ", isInQueue[i]? 1 : 0);
	
	printf("\n\n\n\ninQueue:\n");
	for(int i=1 ; i<=nrNoduri ; ++i)
		printf("%d ", inQueue[i]);
}

*/