#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

const int NMax = 5 * 1e4, oo = 0x3f3f3f3f;

struct Graph{
    int ngh, cost;
};
vector <Graph> g[NMax + 5];
queue <int> q;
int n, m;
int dist[NMax + 5], timesinq[NMax + 5];
bool inq[NMax + 5];

void Read(){
    fin >> n >> m;
    while (m--){
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({y, c});
    }
}

int BellmanFord(){
    memset(dist, oo, sizeof dist);
    dist[1] = 0;
    q.push(1);
    inq[1] = 1;
    timesinq[1]++;
    while (!q.empty()){
        int node = q.front();
        q.pop();
        for (auto edge : g[node]){
            int ngh = edge.ngh, cost = edge.cost;
            if (dist[ngh] > dist[node] + cost){
                dist[ngh] = dist[node] + cost;
                if (inq[ngh])
                    continue;
                q.push(ngh);
                inq[ngh] = 1;
                timesinq[ngh]++;
                if (timesinq[ngh] == n)
                    return 0;

            }
        }
        inq[node] = 0;
    }
    return 1;
}

void Print(){
    if (!BellmanFord()){
        fout << "Ciclu negativ!" << '\n';
        return;
    }
    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    fout << '\n';
}

int main(){
    Read();
    Print();
    return 0;
}