#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int, int>> graf[50010];
int minim[50010], n, m;
priority_queue<pair<int, int>> q;

int bf(int start){
    minim[start] = 0;

    for (int j = 1; j <= n; j++) {
        for (auto &vecin : graf[j]) {
            int nextnod = vecin.first;
                int cost = vecin.second;
                if (minim[j] + cost < minim[nextnod]) {
                minim[nextnod] = minim[j] + cost;
            }
        }
    }

    for (int j = 1; j <= n; j++) {
        for (auto &vecin : graf[j]) {
            int nextnod = vecin.first;
            int cost = vecin.second;
            if (minim[j] + cost < minim[nextnod]) {
                fout << "Negative cycle detected" << endl;
            return 0;
            }
        }
    }
    return 1;
}

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

    for (int i = 1; i <= n; i++)
        minim[i] = 1e9;

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

    if (bf(1)==1)
        for(int i=2; i<=n; i++){
            fout<<minim[i]<<' ';
    }
}