#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define inf 1000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int main()
{
    int v,e,s;
    fin>>v>>e;
    s=1;

    vector<pair<int,int>> m[50001];

    for(int i=1;i<=e;i++){
        int x,y,val;
        fin>>x>>y>>val;
        m[x].push_back({val,y});
    }

    int d[50001];
    set<int> relaxed_vertices;
    for(int i=1;i<=v;i++)
        d[i]=inf, relaxed_vertices.emplace(i);//, t[i]=inf;
    d[s]=0;


    for(int relaxari=1;relaxari<v;relaxari++){
        set<int> temp_relaxed;
        for(int vf:relaxed_vertices){
            if(d[vf]==inf) continue;

            for(auto val_m:m[vf]){
                int urm=val_m.second;
                int val=val_m.first;

                if(d[urm]>d[vf]+val){
                    d[urm]=d[vf]+val;
                    temp_relaxed.emplace(urm);
                }
            }
        }
        relaxed_vertices=temp_relaxed;
    }

    for(int vf=1;vf<=v;vf++){
            for(auto val_m:m[vf]){
                int urm=val_m.second;
                int val=val_m.first;

                if(d[urm]>d[vf]+val){
                    //ciclu negativ
                    fout<<"Ciclu negativ!";
                    return 0;
                    /*
                    t[urm]=vf;

                    bool viz[10001]={};
                    viz[urm]=1;
                    while(!viz[vf]){
                        viz[vf]=1;
                        vf=t[vf];
                    }

                    vector<int> ciclu;
                    ciclu.push_back(vf);
                    vf=t[vf];
                    while(vf!=urm){

                    }
                    */
                }
            }
        }

    for(int i=2;i<=v;i++)
        fout<<d[i]<<' ';
    return 0;
}