#include <bits/stdc++.h>
#define NMAX 50005
#define INF 1000000000
#define cst first
#define nod second

using namespace std;

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

int n,m;
vector < pair<int,int> > mv[NMAX];
vector <int> cntinq(NMAX,0);
vector <int> cost(NMAX,INF);
queue <int> q;

int main(){
    int i,x,y,c,negativeCycle=0;

    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        mv[x].push_back(make_pair(c,y));
    }

    bitset <NMAX> inq(0);

    q.push(1);
    inq[1]=1;
    cost[1]=0;

    while(!q.empty() && !negativeCycle){
        x=q.front();
        q.pop();

        inq[x]=0;

        for(i=0;i<mv[x].size();i++)
            if(cost[mv[x][i].nod]>mv[x][i].cst+cost[x]){
                cost[mv[x][i].nod]=mv[x][i].cst+cost[x];

                if(!inq[mv[x][i].nod]){
                    if(cntinq[mv[x][i].nod]>n)
                        negativeCycle=1;
                    else{
                        cntinq[mv[x][i].nod]++;
                        inq[mv[x][i].nod]=1;
                        q.push(mv[x][i].nod);

                    }
                }
            }
    }

    if(negativeCycle)
        fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            fout<<cost[i]<<" ";

    return 0;
}