#include <fstream>
#include <vector>
#include <queue>
#define inf 250000003

using namespace std;

int n, i, x, y, c, nr[50001], m, d[50001], crt, nod;
vector<pair<int, int> > v[50001];
queue<int> q;
char f[50001];

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

int main(){
    /// initial, toate distantele de la 1 la celelalte noduri sunt infinite, dar distanta pana la el insusi e nula
    /// plec de la varful 1
    /// mai intai, ajung in vecinii lui
    /// deocamdata, costul minim pana la fiecare e chiar costul muchiei dintre 1 si vecin
    /// actualizez acest cost si pun in coada vecinii lui 1, deoarece am modificat informatiile despre ei
    /// DAR pun un vecin in coada daca nu este deja acolo (cand ajung la el in coada, costul pana la el va fi deja actualizat)
    /// mai departe, pentru ca am in coada elemente actualizate inca neexplorate, pornesc din fiecare element din coada prin vecinii lui
    /// si asa mai departe
    /// dupa ce explorez un nod, il scot din coada
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y, c));
    }
    d[1] = 0;
    for(i=2;i<=n;i++)
        d[i] = inf;
    q.push(1);
    f[1] = 1;
    while(!q.empty()){
        crt = q.front();
        for(i=0;i<v[crt].size();i++){
            nod = v[crt][i].first;
            if(d[crt] + v[crt][i].second < d[nod]){
                d[nod] = d[crt] + v[crt][i].second;
                nr[nod]++;
                if(nr[nod] == n-1){
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                if(f[nod] == 0){
                    q.push(nod);
                    f[nod] = 1;
                }
            }
        }
        q.pop();
        f[crt] = 0;
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}