#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int N = 5e4 + 1, INF32 = 0x3f3f3f3f;
int n, m, x, y, w, dist[N], cnt[N];
vector<pair<int, int>> c[N];
queue<int> q;
bool inCoada[N];

bool spfa(int start){ // Shortest Path Faster Algorithm
    for(int i = 2; i <= n; i++)
        dist[i] = INF32;

    q.push(start);
    inCoada[start] = 1;
    cnt[start] = 1;
    while(!q.empty()){
        x = q.front();
        q.pop();
        inCoada[x] = 0;
        for(auto muc: c[x]){
            y = muc.first, w = muc.second;
            if(dist[y] > dist[x] + w){
                dist[y] = dist[x] + w;
                if(!inCoada[y]){
                    q.push(y);
                    inCoada[y] = 1;
                    cnt[y]++;
                    if(cnt[y] == n)
                        return 0;
                }
            }
        }
    }

    return 1;
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++){
        f >> x >> y >> w;
        c[x].push_back({y, w});
    }

    f.close();
    if(!spfa(1)){
        g << "Ciclu negativ!";
        g.close();
        return 0;
    }

    for(int i = 2; i <= n; i++)
        g << dist[i] << ' ';

    g.close();
}