#include <fstream>
#include <vector>
#include <queue>

#define pii pair<int, int>
#define NMAX 50010
#define fs first
#define sc second
#define inf 2000000000

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

queue <int> q;
vector <pii> v[NMAX];

int cost[NMAX], ap[NMAX];
int n, m, x, y, c;

void bf(int x){
    for(int i = 1; i <= n; i++) cost[i] = inf;
    q.push(x);
    cost[x] = 0;
    while(!q.empty()){
        x = q.front();
        ap[x]++;

        if(ap[x] >= n){
            fout << "Ciclu negativ!";
            return;
        }

        q.pop();
        int nr = v[x].size();

        for(int i = 0; i < nr; i++){
            if(cost[x] + v[x][i].sc < cost[v[x][i].fs]){
                cost[v[x][i].fs] = cost[x] + v[x][i].sc;
                q.push(v[x][i].fs);
            }
        }
    }

    for(int i = 2; i <= n; i++){
        fout << cost[i] << ' ';
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }

    bf(1);

    return 0;
}