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

using namespace std;

FILE *in,*out;
//definitii
#define pb push_back
#define mp make_pair
#define node first
#define cost second


//constante
const int Nmax=(int)5e4+1;
const int oo=(1<<30)-1;

//variabile
int noduri,muchii;
int nod1,nod2,rcost;
int dist[Nmax];
int inQueueTimes[Nmax];
bool inQueue[Nmax];
vector<pair<int,int> > graph[Nmax];
queue<int> q;

int main(void)
{
	in=fopen("bellmanford.in","rt");
	fscanf(in,"%d%d",&noduri,&muchii);
	while(muchii--)
	{
		fscanf(in,"%d%d%d",&nod1,&nod2,&rcost);
		graph[nod1].pb(mp(nod2,rcost));		
	}
	fclose(in);
	for(int i=2;i<=noduri;++i)
		dist[i]=oo;
	
	q.push(1);
	inQueue[1]=true;
	while(!q.empty())
	{
		int curent=q.front();
		q.pop();
		inQueue[curent]=false;
		vector<pair<int,int> > :: iterator it,end=graph[curent].end();
		for(it=graph[curent].begin() ; it!=end ; ++it)
		{
			if(dist[curent]+it->cost < dist[it->node])
			{
				dist[it->node]=dist[curent]+it->cost;
				if(inQueue[it->node])
					continue;
				q.push(it->node);
				inQueue[it->node]=true;
				if(++inQueueTimes[it->node] > noduri)
				{	
					out=fopen("bellmanford.out","wt");
					fprintf(out,"Ciclu negativ!\n");
					fclose(out);
					return 0;
					
				}	
				
				
			}	
		}	
	}
	out=fopen("bellmanford.out","wt");
	for(int i=2;i<=noduri;++i)
		fprintf(out,"%d ",dist[i]);	
	fclose(out);
	return 0;
}