#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m;

struct muchie
{
    int x,c;
};

vector<muchie>a[50001];
int d[50001],vz[50001],cnt[50001];

int main()
{
    int i,x,y,z,ok=1;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x].push_back({y,z});
    }

    for(i=1;i<=n;i++)d[i]=INF;

    queue<int>q;
    q.push(1);
    d[1]=0;
    cnt[1]=1;
    vz[1]=1;

    while(!q.empty() && ok==1)
    {
        int s=q.front();
        q.pop();
        vz[s]=0;
        for(auto u:a[s])
            if(d[u.x]>d[s]+u.c)
            {
                d[u.x]=d[s]+u.c;
                if(vz[u.x]==0)
                {
                    q.push(u.x);
                    vz[u.x]=1;
                    cnt[u.x]++;
                    if(cnt[u.x]==n)
                    {
                        ok=0;
                        break;
                    }
                }
            }
    }
    if(ok==0)
        g<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++)g<<d[i]<<' ';
    }
    return 0;

}