#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>

using namespace std;

FILE *in,*out;

//definitions
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cost first
#define to second

//constants
const int sz = (int) 5e4+1;
const int oo = (1<<30)-1;

//variables
int nodes, edges;
int node1, node2, weight;

vector<pii> graph[sz];

int dist[sz];

queue<int> q;

bool inQueue[sz];
int inQueueTimes[sz];

//functions

int main(void)
{
	in = fopen("bellmanford.in", "rt");
	out = fopen("bellmanford.out","wt");
	
	fscanf(in, "%d%d", &nodes, &edges);
	
	while(edges--)
	{
		fscanf(in, "%d%d%d", &node1, &node2, &weight);
		graph[node1].pb(mp(weight,node2));
	}
	
	dist[1] = 0;
	for(int i=2; i<=nodes; ++i)
		dist[i] = oo;
	
	inQueue[1] = true;
	q.push(1);
	
	while (!q.empty())
	{
		int current = q.front();
		q.pop();
		inQueue[current] = false;
		
		vector<pii> :: iterator it, end=graph[current].end();
		
		for( it=graph[current].begin(); it!=end; ++it)
		{
			if( dist[it->to] > dist[current] + it->cost)
			{
				dist[it->to] = dist[current] + it->cost;
				if(inQueue[it->to])
					continue;
				q.push(it->to);
				inQueue[it->to] = true;

				if(++inQueueTimes[it->to] > nodes)
				{
					fprintf(out, "Ciclu negativ!\n");
					fclose(in);
					fclose(out);
					return 0;
				}
			}
		}
	}
	
	for(int i=2; i<=nodes; ++i)
			fprintf(out, "%d ", dist[i]);
		
	fclose(in);
	fclose(out);
	return 0;
}