#include <bits/stdc++.h>
#define INF 999999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, a, b, d, p, u;
vector< pair<int, int> > g[50010];
int coada[50010], viz[50010], dist[50010], decateori[50010], ok=1;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>d;
        g[a].push_back(make_pair(b, d));
    }

    for(int i=1;i<50000;i++)
        dist[i]=INF;

    p=u=1;
    coada[1]=1;
    dist[1]=0;
    while(p<=u)
    {
        decateori[coada[p]]++;
        if(decateori[coada[p]]==n-1)
        {break;ok=0;}

        for(int i=0;i<g[coada[p]].size();i++)
            if(dist[coada[p]]+g[coada[p]][i].second<dist[g[coada[p]][i].first])
        {
            dist[g[coada[p]][i].first]=dist[coada[p]]+g[coada[p]][i].second;

            if(!viz[g[coada[p]][i].first])
            {
                viz[coada[p]]=1;
                coada[++u]=g[coada[p]][i].first;
            }
        }
        viz[coada[p]]=0;
        p++;
    }
    if(!ok)
        fout<<"Ciclu negativ!";
    else
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<' ';
    return 0;
}