#include <bits/stdc++.h>
#define N 50007
using namespace std;

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

int n,m;
vector<pair<int,int>>g[N];
void BelmanFord(int start)
{
    bool ciclu_negativ=0;
    vector<int> dist(N,0);
    bitset<N>accesibil;
    dist[start]=0;
    accesibil[start]=1;

    for(int l=1;l<=n;l++)
    {
        bool ajustare=0;
        for(int x=1;x<=n;x++)
        {
            if( !accesibil[x] )continue;
            for(auto w:g[x])
            {
                int y=w.second;
                int c=w.first;

                if( !accesibil[y] or dist[y]>dist[x]+c )
                {
                    accesibil[y]=1;
                    dist[y]=dist[x]+c;
                    ajustare=1;
                }
            }
        }
        if( ajustare and l==n )
            ciclu_negativ=1;
    }

    if( ciclu_negativ )
        fout << "Ciclu negativ!\n";
    else
        for(int i=1;i<=n;i++)
            if( i!=start )
                fout << dist[i] << " ";
}

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        g[x].push_back({c,y});
    }
    BelmanFord(1);
    fin.close();fout.close();
    return 0;
}