#include <fstream>
#include <deque>
#include <vector>
#define x first
#define y second
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

deque <int> c;
vector < pair<int,int> > l[50001];
int n,m,i,j,k,cost,nod,vecin,v[50001],N[50001],d[50001];

int main(){
    fin>>n>>m;
    for(k=1;k<=m;k++){
        fin>>i>>j>>cost;
        l[i].push_back( make_pair(j,cost) );
    }

    for(i=2;i<=n;i++)
        d[i]=1000000;
    d[1]=0; v[1]=1;
    c.push_back(1);

    while(!c.empty()){
        nod=c.front();
        c.pop_front(); v[i]=0;

        for(i=0;i<l[nod].size();i++){
            vecin=l[nod][i].x;
            if(d[vecin]>d[nod]+l[nod][i].y){
                d[vecin]=d[nod]+l[nod][i].y;

                ///ciclu negativ
                N[vecin]++;
                if(N[vecin]>n){
                    fout<<"Ciclu negativ";
                    return 0;
                }
            }

            if(v[vecin]==0){
                v[vecin]=1;
                c.push_back(vecin);
            }
        }
    }

    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";

    return 0;
}