#include <bits/stdc++.h>
#define MAX 50000007
#define N 50007

using namespace std;


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

int n,m;
bool ok;
vector<int>dist(N,MAX);
vector <pair<int,int>>a[N];

void Citire()
{
    fin >> n >> m ;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x].push_back( {c,y} );
    }
    fin.close();
}

void Update(int x)
{
    for(auto y:a[x])
        if( dist[y.second]>dist[x]+y.first )
        {
            ok=0;
            dist[y.second]=dist[x]+y.first;
        }
}

void Belman_Ford()
{
    dist[1]=0;
    for(int l=1;l<=n and !ok;l++)
    {
        ok=1;
        for(int i=1;i<=n;i++)
            Update(i);
    }
    if( !ok )
        fout << "Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout << dist[i] << " ";
}



int main()
{
    Citire();
    Belman_Ford();
    return 0;
}