#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<=m; 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();
        for(j=0; j<v[nod].size(); j++) {
            if(t[v[nod][j].first]>t[nod]+v[nod][j].second) {
                t[v[nod][j].first]=t[nod]+v[nod][j].second;
                if(viz[v[nod][j].first]==0)  {
                    viz[v[nod][j].first]=1;
                    h.push(v[nod][j].first);
                    ct[v[nod][j].first]++;
                    if(ct[v[nod][j].first]>n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        h.pop();
        viz[nod]=0;
    }
    for(i=2;i<=n; i++) {
        fout<<t[i]<<" ";
    }
        return 0;
    }