#include <fstream>
#include <vector>
#define oo 999999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector < vector < pair <int, int> > > v;
vector <int> d;
int n, m;
int main()
{
    fin>>n>>m;
    int x, y, z;
    v.resize(n + 1);
    d.resize(n + 1, oo);
    for (int i = 1; i <= m; i++) {
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y, z));
    }
    int R = 1;
    d[R] = 0;
    for(int k = 1; k <= n - 1; k++) {
        for (int i = 1; i <= n; i++) {
            if (d[i] != oo) {
                for (int j = 0; j < v[i].size(); j++) {
                    if (v[i][j].second + d[i] < d[v[i][j].first]) {
                        d[v[i][j].first] = v[i][j].second + d[i];
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] != oo) {
            for (int j = 0; j < v[i].size(); j++) {
                if (v[i][j].second + d[i] < d[v[i][j].first]) {
                    fout<<"Ciclu negativ!";
                    return 1;
                }
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout<<d[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}