#include<bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int oo = 1<<30;
const int N =50002;
bitset<N> q;
vector<pair<int,int> > v[N];
queue<int> Q;
int n,cnt[N],d[N];

int main()
{
	int x,y,c,m;
	f>>n>>m;
	for(;m;m--)
	{
	    f>>x>>y>>c;
	    v[x].push_back(make_pair(y,c));
	}
	for(int i=2;i<=n;i++)d[i]=oo;
	Q.push(1);
	d[1]=0;
	q[1]=1;
	for(;Q.size();Q.pop())
	{
	    int nod=Q.front();
		for(auto it:v[nod])
        {
            int vec,cstMuchie;
            tie(vec,cstMuchie)=it;
			if(d[nod]+cstMuchie<d[vec])
			{
				if(!q[vec])
				{
					q[vec]=1;cnt[vec]++;
					if(cnt[vec]>n)
					{
						g<<"Ciclu negativ!\n";
						return 0;
					}
					Q.push(vec);
				}
				d[vec]=d[nod]+cstMuchie;
			}
        }
		q[nod]=0;
	}
	for(int i=2;i<=n;i++)
        g<<d[i]<<' ';
	return 0;

}