#include <fstream>
#include<vector>
#include<queue>
#define inf 999999
#include<string.h>
#include<stdlib.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int,int> > a[50002];
queue<int> q;
int f[50001],d[50001],n,m;
bool v[50001];
void cit(){
    int i,j,h,w;
    fin>>n>>m;
    for(h=1;h<=m;h++){
        fin>>i>>j>>w;
        a[i].push_back(make_pair(j,w));
    }
    fin.close();
}
void bellmanford(){
    int i,k,x;
    q.push(1);
    memset(d,inf,sizeof(d));
    d[1]=0;
    while(!q.empty()){
        k=q.front();
        q.pop();
        v[k]=0;
        for(i=0;i<a[k].size();i++){
            x=a[k][i].first;
            if(d[x]>d[k]+a[k][i].second){
                d[x]=d[k]+a[k][i].second;
                if(v[x]==0){
                    v[x]=1;
                    q.push(x);
                    f[x]++;
                    if(f[x]==n+1){
                        fout<<"Ciclu negativ!";
                        exit(0);
                    }
                }
            }
        }
    }
}
int main(){
    cit();
    bellmanford();
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    fout.close();
    return 0;
}