#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
queue<int> q;
vector<int> v[50001],vc[50001];
int a,i,n,j,m,vcc[50001],vq[50001];
int main ()
{
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    v[x].push_back(y);
    vc[x].push_back(z);
    }
for(i=2;i<=n;i++)
    vcc[i]=1000000000;
q.push(1);
int pp=0;
while(!q.empty())
    {
    int h=q.front();
    if(vq[h]==n+1)
        {
        pp=1;
        break;
        }
    for(i=0;i<v[h].size();i++)
        if(vcc[v[h][i]]>vcc[h]+vc[h][i])
            {
            q.push(v[h][i]);
            vcc[v[h][i]]=vcc[h]+vc[h][i];
            vq[v[h][i]]++;
            }
    q.pop();
    }
if(pp==1)
    printf("Ciclu negativ!");
else
    for(i=2;i<=n;i++)
        printf("%d ",vcc[i]);
return 0;
}