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

using namespace std;
vector<pair<int, int> >v[50001];
queue<int>h;
int t[50001], ct[50001];
bool viz[50001];
int main(){
    int i, n, x, y, c, j, nod, newn, m, cost;

    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for(i=1; i<=n; i++){
        fin>>x>>y>>c;
        v[x].push_back({y, c});
    }
    for(i=1; i<=n; i++) {
        t[i]=1e9;
    }
    h.push(1);
    t[1]=0;
    viz[1]=1;
    ct[1]++;
    while(!h.empty()) {
        nod=h.front();
         h.pop();
        for(j=0; j<v[nod].size(); j++) {
            newn=v[nod][j].first;
            cost=v[nod][j].second;
            if(t[newn]>t[nod]+cost) {
                t[newn]=t[nod]+cost;
                if(viz[newn]==0)  {
                    viz[newn]=1;
                    h.push(newn);
                    ct[newn]++;
                    if(ct[newn]>n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        viz[nod]=0;
    }
    for(i=2;i<=n; i++) {
        fout<<t[i]<<" ";
    }
        return 0;
    }