#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf (1<<30)
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector < pair < int , int > > arbore[250005];
int n,m,x,y,c,viz[50005],d[50005];
queue < int > q;
void bellmanford(){
    for(int i=2;i<=n;++i) d[i]=inf;
    d[1]=0;
    q.push(1);
    while(!q.empty()){
        int nod=q.front();
        q.pop();
        viz[nod]++;
        if(viz[nod]>n) {out<<"Ciclu negativ!"<<'\n';return;}
        vector < pair < int , int > > ::iterator it;
        for(it=arbore[nod].begin();it!=arbore[nod].end();it++){
            int vecin=it->first;
            int cost=it->second;
            if(d[vecin]>d[nod]+cost){
               d[vecin]=d[nod]+cost;
               q.push(vecin);
            }
        }

    }
    for(int i=2;i<=n;++i) {
        if(d[i]==inf) out<<0<<' ';
        else out<<d[i]<<' ';
    }
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i){
        in>>x>>y>>c;
        arbore[x].push_back(make_pair(y,c));
    }
    bellmanford();
    return 0;
}