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

using namespace std;

#define Nmax 50001
#define INF 0x3f3f3f

int N, M, D[Nmax], cnt[Nmax];
vector<pair<int, int> > G[Nmax];
bitset<Nmax> viz;
queue<int> Q;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int main() {
	int nod, fiu, cost, i, j, c;
	
	f>>N>>M;
	while(M--) {
		f>>i>>j>>c;
		G[i].push_back(make_pair(j,c));
	}
	for(i=1; i<=N; i++)
		D[i]=INF;
	Q.push(1); D[1]=0; viz[1]=1;
	while(!Q.empty()) {
		nod=Q.front();
		for(vector<pair<int, int> >:: iterator it=G[nod].begin(); it!=G[nod].end(); ++it) {
			fiu=it->first; cost=it->second;
			if(D[fiu]>D[nod]+cost) {
				D[fiu]=D[nod]+cost;
				if(!viz[fiu]) {
					cnt[fiu]++;
					if(cnt[fiu]>N) {
						g<<"Ciclu negativ\n";
						f.close(); g.close();
						return 0;
					}
					Q.push(fiu);
					viz[fiu]=1;
				}
			}
		}
		viz[nod]=0;
		Q.pop();
	}
	for(i=2; i<=N; i++)
		g<<D[i]<<" ";
	
	f.close(); g.close();
	
	return 0;
}