#include<fstream>
#include<vector>
#include<queue>
using namespace std;
vector <pair<unsigned short,short> > v[50010];
queue <unsigned short> q;
bool in_queue[50010];
int n,nr,dist[50010],nr_in_queue[50010],inf=1<<30;
bool bellman_ford() {
	int nod,i,m,vecin,cost,negative_cycle=0;
	while(!q.empty()&&!negative_cycle) {
		nod=q.front();
		in_queue[nod]=false;
		q.pop();
		m=v[nod].size();
		for(i=0;i<m;i++) {
			vecin=v[nod][i].first;
			cost=v[nod][i].second;
			if(dist[nod]+cost<dist[vecin]) {
				dist[vecin]=dist[nod]+cost;
				if(!in_queue[vecin]) {
					q.push(vecin);
					in_queue[vecin]=1;
					nr_in_queue[vecin]++;
					if(nr_in_queue[vecin]>n) {
						negative_cycle=1;
						break;
						}
					}
				}
			}
		}
	if(negative_cycle)
		return 1;
	return 0;
}
void citire() {
	int i,x,y,c,m;
	ifstream in("bellmanford.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		v[x].push_back(pair <unsigned short,short>(y,c));
		}
	for(i=1;i<n;dist[i+++1]=inf);
	in.close();
}
int main() {
	citire();
	q.push(1);
	ofstream out("bellmanford.out");
	if(bellman_ford())
		out<<"Ciclu negativ!";
	else
		for(int i=2;i<=n;out<<dist[i++]<<" ");
	out<<'\n';
		out.close();
	return 0;
}