#include <bits/stdc++.h>
using namespace std;
ifstream  fin("bellmanford.in");
ofstream  fout("bellmanford.out");
typedef long long big;
#define maxn  50000
#define infinit 0x3f3f3f3f
    int n, p, m;
    bool ok = false;
    vector<pair<int, int>> a[maxn + 2];
    int drum[maxn + 2];
    int visited[maxn + 2];
    void read(){
        fin >> n >> m;
        for(int i = 1; i <= m; ++i){
            int x, y, cost;
            fin >> x >> y >> cost;
            a[x].push_back({y, cost});

        }
    }
    void dijkstra(){
        queue<int> q;
        q.push(1);
        while(!q.empty()){
            int nod = q.front();
            visited[nod] ++;
            if(visited[nod] >= n){
                fout << "Ciclu negativ!";
                ok = true;
                return ;
            }
            for(auto x : a[nod])
                if(x.second + drum[nod] < drum[x.first]) drum[x.first] = x.second + drum[nod], q.push(x.first);
            q.pop();
        }
    }
int main(){
    read();
    for(int i = 2; i <= n; ++i)
        drum[i] = infinit;
    dijkstra();
    if(!ok)
        for(int i = 2; i <= n; ++i){
            if(drum[i] == infinit) fout << 0;
            else fout << drum[i];
            fout << " ";
        }

    return 0;
}