#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int inf = 1073741824;

int n, m;
vector<pair<int, int> > vecini[50005];
int viz[50005];
int sol[50005];

void citire(){
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
        tmp1--;
        tmp2--;
        vecini[tmp1].push_back({tmp2, tmp3});
    }

    for(int i = 0; i < n; i++){
        sol[i] = inf;
    }
}

int solve(){
    queue<pair<int, int> > Q;
    Q.push({0, 0});
    sol[0] = 0;

    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        viz[x]++;

        if(viz[x] > n){
            printf("Ciclu negativ!");
            return 0;
        }

        int l = vecini[x].size();

        for(int i = 0; i < l; i++){
            int d = sol[x] + vecini[x][i].second;

            if(d < sol[vecini[x][i].first]){
                sol[vecini[x][i].first] = d;
                Q.push({vecini[x][i].first, vecini[x][i].second + sol[x]});
            }
        }
    }

    return 1;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    citire();
    if(solve() != 0){
        for(int i = 1; i < n; i++){
            printf("%d ", sol[i]);
        }
    }

    return 0;
}