#include <fstream>
#include <vector>
using namespace std;

#define Nmax 50011
#define Mmax 250011

#define val first
#define key second

#define oo 1<<30

vector< pair<int,int> > A[Nmax];
vector< pair<int,int> > Aux;
vector< int > Q;
int Cost[Nmax],N,M;
bool Used[Nmax];
int Times[Nmax];

ifstream F("bellmanford.in");
ofstream G("bellmanford.out");

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int a,b,c;
		F>>a>>b>>c;
		A[a].push_back( make_pair( c , b ) );
	}
	for (int i=1;i<=N;++i)
		Cost[i]=oo;
	
	int Start=1;
	Cost[Start]=0;
	Q.push_back( Start );
	Used[Start]=1;
	
	while ( Q.size() )
	{
		int Nbr=Q.back();
		Q.pop_back();
		Used[Nbr]=0;
		
		while ( A[Nbr].size() )
		{
			Aux.push_back( A[Nbr].back() );
			A[Nbr].pop_back();
			
			if ( Cost[Aux.back().key] > Cost[Nbr] + Aux.back().val )
			{
				Cost[Aux.back().key] = Cost[Nbr] + Aux.back().val ;
				
				if ( !Used[ Aux.back().key ] )
				{
					Q.push_back( Aux.back().key );
					Used[ Aux.back().key ]=1;
					
					if ( ++Times[ Aux.back().key ] > N )
					{
						G<<"Ciclu negativ!\n";
						return 0;
					}
				}
			}
		}
		
		while ( Aux.size() )
		{
			A[Nbr].push_back( Aux.back() );
			Aux.pop_back();
		}
	}
	
	for (int i=2;i<=N;++i)
		G<<Cost[i]<<' ';
	G<<'\n';
}