#include <cstdio>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;

#define N 50005
#define inf 1<<30

struct nod {
	int varf;
	int cost;
	};
	
vector<nod> v[N];
int c[N];
bool vrf[N];

void bellmanford (int n){
	
	vector<int> d(n+1,inf);
	d[1]=0;
	queue<int> q;
	++c[1];
	vrf[1]=true;
	for(q.push(1);!q.empty();q.pop()){
		int x=q.front();
		vrf[x]=false;
		for(vector<nod>::iterator i=v[x].begin();i<v[x].end();++i){
			if(d[x]+(*i).cost<d[(*i).varf]){
				d[(*i).varf]=d[x]+(*i).cost;
				if(!vrf[(*i).varf]){
					q.push((*i).varf);
					vrf[(*i).varf]=true;
					++c[(*i).varf];
					if(c[(*i).varf]==n){
						printf("Ciclu negativ!\n");
						exit(0);
						}			
					}
				}
			}
		}
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]);
	printf("\n");
	
	}

int main ()
{
	
	ifstream in ("bellmanford.in");
	freopen ("bellmanford.out","w",stdout);
	int n,m;
	in>>n>>m;
	for(int x,y,z;m;--m){
		in>>x>>y>>z;
		v[x].push_back((nod){y,z});
		}
	bellmanford (n);	
	
	return 0;}