#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
int inf=1<<30; 
int n,m,dist[50005],use[50005],acum,y,c,i,x;
struct arc{int nod,cost;};
vector <arc> l[50005];
queue <int> q;
int main(){
    f>>n>>m;
    while(m--){   f>>x>>y>>c; l[x].push_back((arc){y,c});}
    for(i=2; i<=n; i++) dist[i]=inf;
    q.push(1); 
    while(!q.empty()){
		acum=q.front(); q.pop();
		use[acum]++;
		if(use[acum]==n){g<<"Ciclu negativ!\n"; return 0;}
		for(unsigned int i=0;i<l[acum].size();++i){
			if(dist[l[acum][i].nod]>dist[acum]+l[acum][i].cost){
				dist[l[acum][i].nod]=dist[acum]+l[acum][i].cost;
				q.push(l[acum][i].nod);
			}
		}
	}
    for(i=2; i<=n; i++) g<<dist[i]<<" ";
    g<<"\n";  return 0;
}