#include<fstream>
#include<vector>
struct muchie{
int x,y, c;};
using namespace std;
vector<muchie> muchii;
int main(){
    int x,y,c;
    int n,m;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    vector<long> d(n+1,1e9);
    vector<int> viz(n+1,0);
    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        muchii.push_back({x,y,c});
    }
    int s=1;
    d[s]=0;
    int ok=1;
    for(int k=1;k<=n-1;k++){
        if(ok==0) break;
        ok=0;
        for(int i=0;i<m;i++){
            muchie m=muchii[i];
            if(viz[m.x]==k-1)
                if (d[m.x]+m.c<d[m.y]){
                    d[m.y]=d[m.x]+m.c;
                    viz[m.y]=k;
                    ok=1;
                }
        }
    }
    int i;
    if(ok==1){
    for(i=0;i<m;i++){
            muchie m=muchii[i];
            if (d[m.x]+m.c<d[m.y]){
                g<<"Ciclu negativ!";
                break;
            }
        }
    if(i==m){
        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
    }}
    else{
        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
    }



}