#include<fstream>
#include<queue>
#include<vector>
#include<bitset>

using namespace std; 

const int MAX = 50010;
const int inf = 0x3f3f3f3f;

int n,m;
vector < pair <int,int> > M[MAX];
vector <int> Cnt(MAX, 0);
vector <int> dist(MAX, inf); 
bitset < MAX > viz(false);
queue  <int> Q;

int main(){

		ifstream f("bellmanford.in");
		ofstream g("bellmanford.out");
		int i,y,c,x;
		
		f>>n>>m;
		for(i=1;i<=m;i++){
			f>>x>>y>>c;
			M[x].push_back( make_pair(y,c) );
		}
		
	
		Q.push(1);
		viz[1]=true;
		dist[1]=0;
		Cnt[1]=1;
		
		while( !Q.empty() ){
			
			int x = Q.front();
			Q.pop();
			viz[x] = false;
			
			vector< pair<int,int> >::iterator it;
			for( it = M[x].begin(); it!=M[x].end();it++){
				
					if( dist[it->first] > dist[x] + it->second){
						dist[it->first] = dist[x] + it->second;
						Q.push(it->first);
					    viz[it->first]=true;
						Cnt[it->first]++;
					}
					
				if(Cnt[it->first] >= n ){ g<<"Ciclu negativ!\n"; return 0; }
				
			}
		}
		
	for(i=2;i<=n;i++) g<<dist[i]<<" ";
	
	return 0;
}