#define nume "bellmanford"

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>

using namespace std;

//#define _PARSARE_
#ifdef _PARSARE_
#define DIM 8192
char ax[DIM+16];
int idx;
inline void cit(int &x)
{
    x=0;
    while((ax[idx]<'0' || ax[idx]>'9') && (ax[idx]!='-'))
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;

    int neg=0;
    if(ax[idx]=='-') {
        neg=1;
        if(++idx==DIM)fread(ax, 1, DIM, stdin),idx=0;
    }

    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
    if(neg) x=-x;
}
#else
ifstream fin (nume  ".in");
#endif //_PARSARE_
ofstream fout(nume  ".out");
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//#endif

#define foreach(it, v) for (typeof((v).begin()) it = (v).begin(),stop=(v).end(); it != stop; ++it)

int n,m;

vector<pair<int,int> > G[50000+10];
queue<int> Q;
int cnt_in_queue[50000+10];
bool in_queue[50000+10];
int d[50000+10];
bool negative_cycle=false;

inline void bellmanford()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    Q.push(1);
    in_queue[1]=true;
    cnt_in_queue[1]=1;
    while(!Q.empty()) {
        int nod=Q.front();
        Q.pop();
        in_queue[nod]=false;
        foreach(it,G[nod]) {
            if( d[nod]+it->second<d[it->first] ) {
                d[it->first]=d[nod]+it->second;
                
                if(!in_queue[it->first]){
                    Q.push(it->first);
                    in_queue[it->first]=true;
                    
                    if(++cnt_in_queue[it->first]>n+1) {
                        fout<<"Ciclu negativ!\n";
                        exit(0);
                    }
                }
            }
        }
    }
}

inline void Bellmanford() {
    memset(d,0x3f,sizeof(d));
    memset(in_queue,false,sizeof(in_queue));
    queue<int> Q;

    d[1]=0;
    in_queue[1]=true;
    Q.push(1);
    while(!Q.empty()&&!negative_cycle) {
        int nod=Q.front();
        in_queue[nod]=false;
        Q.pop();
        foreach(it,G[nod]){
            if( d[it->first] > d[nod] + it->second ) {
                d[it->first] = d[nod] + it->second;

                if(!in_queue[it->first]) {
                    if(cnt_in_queue[it->first]>n) { //ciclu negativ
                        cout<<"Ciclu negativ!"<<'\n';
                        negative_cycle=true;
                        return;
                    }
                    Q.push( it->first );
                    in_queue[it->first]=true;
                    cnt_in_queue[it->first]++;
                }
            }
        }

    }

}

int main()
{
#ifdef _PARSARE_
    freopen(nume  ".in","r",stdin);
    cit(n);
#endif
    fin>>n>>m;
    for(int i=0; i<m; ++i) {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }

    Bellmanford();
    if(!negative_cycle){
        for(int i=2; i<=n; ++i)
            fout<<((d[i]!=0x3f3f3f3f)?d[i]:0)<<' ';
        fout<<'\n';
    }


    fout.close();
    return 0;
}