#include <queue>
#include <fstream>
#include <vector>
using namespace std;

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

int n, m, i, j, x, y, c, k, d[50100], v[50100], minim, nod2, cost, nod, f[50100];
vector< pair<int,int> >a[50100];
queue <int> s;
const int inf=(1<<30);

int main(){
    fin>>n>>m;
    for (i=1; i<=m; i++){
        fin>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
    for(i=2; i<=n; i++){
        d[i]=inf;
    }
    s.push(1);
    while(!s.empty()){
        nod=s.front();
        f[nod]++;
        v[nod]=0;
        if(f[nod]>n){
            fout<<"Ciclu negativ!";
            return 0;
        }
        s.pop();
        for(i=0; i<a[nod].size();i++){
            nod2=a[nod][i].first;
            if(a[nod][i].second+d[nod]<d[nod2]){
                d[nod2]=a[nod][i].second+d[nod];
                if(v[nod2]==0){
                    v[nod2]=1;
                    s.push(nod2);
                }
            }
        }
    }
    for(i=2; i<=n; i++){
        if(d[i]!=inf){
            fout<<d[i]<<" ";
        }else{
            fout<<0<<" ";
        }
    }
}