#include <fstream>
#include <vector>
#define inf 1<<29
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n,m,i,x,y,cost,d[2500010],c[500010],v[250010],p,u,nod,B[250010],nodv;
vector <pair<int,int> > L[250010];
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    c[1]=1;
    v[1]=1;
    p=u=1;
    while(p<=u){
        nod=c[p];
        B[nod]++;
        if(B[nod]>=n){
            fout<<"Ciclu negativ!";
            return 0;
        }
        for(i=0;i<L[nod].size();i++){
            nodv=L[nod][i].first;
            cost=L[nod][i].second;
            if(d[nodv]>d[nod]+cost){
                d[nodv]=d[nod]+cost;
                if(v[nodv]==0){
                    v[nodv]=1;
                    c[++u]=nodv;
                }
            }
        }
        ++p;
        v[nod]=0;
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
}