#include<iostream>
#include<fstream>
#include<vector>
#include<limits.h>
#include<queue>
#define N 50010
using namespace std;

ifstream f("bellmanford.in");
ofstream o("bellmanford.out");

int n,m,d[N],ap[N];

queue <int> q;
vector <pair<int,int> > v[N];

void citire(){
    f>>n>>m; int i,x,y,c;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
}
void init(){
    d[1]=0;
    int i;
    for(i=2;i<=n;i++)
        d[i]=INT_MAX;
    q.push(1);
}
bool bellman(){
    init(); int i,nod,nv,cv;
    while(q.size()){
        nod=q.front();
        q.pop();
        if(ap[nod]>=n){
            o<<"Ciclu negativ!";
            return 0;
        }
        for(i=0;i<v[nod].size();i++){
            nv=v[nod][i].first;
            cv=v[nod][i].second;
            if(d[nod]+cv<d[nv]){
                ap[nv]++;
                d[nv]=d[nod]+cv;
                q.push(nv);
            }
        }
    }
    return 1;
}
int main(){
    citire(); int i;
    if(bellman())
        for(i=2;i<=n;i++)
            o<<d[i]<<" ";
    o.close();
    f.close();
}