#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
char buff[4096];
int pbuf=4095;
void readbuff(){
    pbuf=0;fin.read(buff,4095);
}
int citire(){
    int nr=0,semn=0;
    if(pbuf==4095){
        semn=0;readbuff();
    }
    while(buff[pbuf]<'0'||buff[pbuf]>'9'){
        if(buff[pbuf]=='-'){
            semn=1;
        }
        pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    while(buff[pbuf]>='0'&&buff[pbuf]<='9'){
        nr=nr*10+buff[pbuf]-'0';pbuf++;
        if(pbuf==4095){
            readbuff();
        }
    }
    if(semn==1){
        nr=-nr;
    }
    return nr;
}
vector<int>G[50005],cost[50005];int n;int gasit=0;
bool inq[50005];int viz[50005],dist[50005];queue<int>q;
void BF(){
   while(!q.empty()){
    int nod=q.front();inq[nod]=0;q.pop();
    if(viz[nod]>n){gasit=1;return;}
    for(int i=0;i<G[nod].size();i++){
        if(dist[G[nod][i]]>dist[nod]+cost[nod][i]){
            dist[G[nod][i]]=dist[nod]+cost[nod][i];
            viz[G[nod][i]]++;
            if(inq[G[nod][i]]==0){inq[G[nod][i]]=1;q.push(G[nod][i]);}
        }
    }
   }
}
int main()
{
    int m,a,b,c;n=citire();m=citire();for(int i=1;i<=n;i++){dist[i]=INT_MAX;}
    for(int i=1;i<=m;i++){
        a=citire();b=citire();c=citire();
        G[a].push_back(b);cost[a].push_back(c);
    }
    inq[1]=1;viz[1]=1;q.push(1);dist[1]=0;BF();
    if(gasit==1){
        fout<<"Ciclu negativ!"<<'\n';
    }
    else{
        for(int i=2;i<=n;i++){
            fout<<dist[i]<<" ";
        }fout<<'\n';
    }
    return 0;
}