#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, node, x, y, val;
struct muchie
{
    int i, j, val;
};
vector < muchie > v;

void READ(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    fin >> n >> m;
    while(fin >> x >> y >> val)
    {
        --x; --y;
        v.push_back({x, y, val});
    }
}

void BELLMAN_FORD(void)
{
    vector < int > dist(n, INT_MAX);
    dist[0] = 0;

    for(int i = 0; i < n - 1; i++)
    {
        for(int j = 0; j < m; j++)
        {
            int x = v[j].i;
            int y = v[j].j;
            int w = v[j].val;
            if(dist[x] != INT_MAX && dist[x] + w < dist[y])
            {
                dist[y] = dist[x] + w;
            }
        }
    }

    for(int j = 0; j < m; j++)
        {
            int x = v[j].i;
            int y = v[j].j;
            int w = v[j].val;
            if(dist[x] != INT_MAX && dist[x] + w < dist[y])
            {
              fout << "Ciclu negativ!";
              exit(0);
            }
        }

    for (int i = 1; i < n; i++) {
        fout << dist[i] << " ";
    }

}

int main()
{
    READ();
    BELLMAN_FORD();


    return 0;
}