#include <iostream>
#include <vector>
#include <fstream>
using namespace std;


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

#define NMAX 100000
#define inf 99999999

int n, m, dist[NMAX];
vector<pair<pair<int, int>, int> > graph;

void citire()
{
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        f>>a>>b>>c;
        graph.push_back(make_pair(make_pair(a,b),c));
    }
}
int ok = 0;
void BellmanFord()
{

    int sursa = 1;
    dist[sursa] = 0;

    for(int i = 2; i <= n; i ++)
        dist[i] = inf;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            int cost = graph[j].second;
            int x = graph[j].first.first;
            int y = graph[j].first.second;
            if(dist[x] + cost < dist[y])
                dist[y] = dist[x] + cost;
        }
    }

    for(int j = 0; j < m; j ++)
    {
        int cost = graph[j].second;
        int x = graph[j].first.first;
        int y = graph[j].first.second;
        if(dist[x] + cost < dist[y])
        {
            dist[y] = dist[x] + cost;
            ok = 1;
        }
    }

}

void afisare()
{
    if(ok == 1)
        g<<"Ciclu negativ!\n";
    else
        for(int i = 2; i <= n; i ++)
            g<<dist[i] <<" ";
}

int main()
{
    citire();
    BellmanFord();
    afisare();
    return 0;
}