#include<cstdio>
#define nmax 50001
#include<vector>
#define INF 250000000
using namespace std;

vector < vector < pair < int , int > > >  v(nmax);
int viz[nmax],dist[nmax],C[5*250100],ok1,cnt[nmax];
int N,M;

void read();
void solve();
void write();

int main()
{
	freopen ("bellmanford.in","r",stdin);
	freopen ("bellmanford.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}

void read()
{
	int i,x,y;
	pair < int , int  > z;
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%d%d%d",&x,&y,&z.second);
		z.first=y;
		v[x].push_back(z);
	}
	for (i=2;i<=N;++i)
        dist[i]=INF;
}

void solve()
{
	vector < pair < int , int > > :: iterator it;
	int sf,in,x,c,p;
	C[1]=1;
	in=sf=1;
	viz[1]=1;
	++cnt[1];
	while (in<=sf)
	{
	    p=C[in];
		for (it=v[p].begin();it!=v[p].end();++it)
		{
			x=(*it).first;
			c=(*it).second;
			if (dist[x]>dist[p]+c)
			{
				dist[x]=dist[p]+c;
				if (!viz[x])
				{
					++sf;
					C[sf]=x;
					++cnt[x];
					if (cnt[x]>N)
					{
					    ok1=1;
					    printf("Ciclu negativ!\n");
					    return;
					    }
					viz[x]=1;
				}
			}
		}
		viz[C[in]]=0;
		++in;
	}
}

void write()
{
	int i;
	if (!ok1)
		for (i=2;i<=N;++i)
			printf("%d ",dist[i]);
}