#include <fstream>
#include <vector>

#define oo 1 << 30

using namespace std;

struct edge{
    int x, y;
    short c;
};
vector< edge > E;

vector<int> L[50005];
int d[50005];
int t[50005];

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

    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        edge aux;
        f >> aux.x >> aux.y >> aux.c;
        E.push_back(aux);
        L[aux.x].push_back(i);
    }

    for(int i = 2; i <= n; i ++)
        d[i] = oo;

    for(int i = 1; i < n; i ++) {
        for(int j = 0; j < m; j ++) {

            if(d[ E[j].y ] > d[ E[j].x ] + E[j].c) {
                d[ E[j].y ] = d[ E[j].x ] + E[j].c;
                t[ E[j].y ] = E[j].x;
            }
        }
    }

    for(int j = 0; j < m; j ++) {

        if(d[ E[j].y ] > d[ E[j].x ] + E[j].c) {
            g << "Ciclu negativ!\n";
            return 0;
        }
    }

    for(int i = 2; i <= n; i ++)
        g << d[i] << " ";
    g << "\n";
    return 0;
}