#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

//vector<int>mu[50001];
struct much{int a;int b;int c;}mu[250001];



int cost[50001];
int main()
{int n,i,j,m,p,d;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
    scanf("%d%d%d",&p,&j,&d);
  //  mu[p].push_back(j);
  mu[i].a=p;
  mu[i].b=j;
  mu[i].c=d;

}
for(i=2;i<=n;i++)cost[i]=19876543;
cost[1]=0;

for(i=1;i<n-1;i++)
{
    for(j=0;j<m;j++)
    {
        if(mu[j].c+cost[mu[j].a]<cost[mu[j].b])cost[mu[j].b]=mu[j].c+cost[mu[j].a];
    }
}
 for(j=0;j<m;j++)
    {
        if(mu[i].c+cost[mu[i].a]<cost[mu[i].b]){printf("Ciclu negativ!");d=5;break; }
    }
if(d!=5)for(i=2;i<=n;i++)printf("%d ",cost[i]);

    return 0;
}