#include<fstream>
#include<vector>
#include<queue>
#define inf 0x3F3F3F3
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
vector <pair<int,int> > a[50001];
queue <int> q;
int n, m, x, y, c, k, viz[50001], d[50001];
int main()
{	f>>n>>m; 
	for(int i = 1; i <= m; i++) {f>>x>>y>>c; a[x].push_back(make_pair(y,c));}
	for(int i = 1; i <= n; i++) d[i]=inf;
	q.push(1); viz[1]=1; d[1]=0;
	while(!(q.empty()))
	{k=q.front();
	 for(int i=0; i < a[k].size(); i++)
		{	int nod=a[k][i].first; int cost=a[k][i].second; y=d[k]+cost;
			if(viz[nod]==0 || y<d[nod])
				{q.push(nod); d[nod]=y; viz[nod]++;
				 if(viz[nod]>n) {g<<"Ciclu negativ!\n"; g.close(); return 0;}
		        }
	    }
	 q.pop();
	}
	for(int i=2; i <= n; i++) g<<d[i]<<' ';
	g<<'\n'; return 0;
}