#include <bits/stdc++.h>
#define maxim 50005
#define inf 10000
using namespace std;

vector <pair<int,int> > graf[maxim];
queue <int> coada;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x, y, z, cost[maxim];
int viz[maxim];
bool ok=1;
int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        cost[i]=inf;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        graf[x].push_back({y,z});
    }
    cost[1]=0;
    coada.push(1);
    viz[1]=1;
    while(!coada.empty() && ok==1)
    {
        int actualNod=coada.front();
        coada.pop();
        for(int i=0; i<graf[actualNod].size() && ok==1; i++)
        {
            if(viz[graf[actualNod][i].first]<n && cost[graf[actualNod][i].first]>cost[actualNod]+graf[actualNod][i].second)
            {
                viz[graf[actualNod][i].first]+=1;
                cost[graf[actualNod][i].first]=cost[actualNod]+graf[actualNod][i].second;
                coada.push(graf[actualNod][i].first);
            }
            else if(viz[graf[actualNod][i].first]>=n)
                ok=0;
        }
    }
    if(ok==1)
    {
        for(int i=2; i<=n; i++)
        {
            fout<<cost[i]<<" ";
        }
    }
    else
    {
        fout<<"Ciclu negativ!";
    }
    return 0;
}