#include<fstream>
#include<queue>
#include<vector>
#define N 50001
#define INF 0x3f3f3f
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

vector< pair<int,int> > v[N];
queue<int> q;
int n,m,x,y,cost,nri,i,d[N];
bool viz[N],nc=false;

int main(){
    in>>n>>m;
    for(i=0;i<m;++i)
    {
        in>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    for(i=2;i<=n;++i)
        d[i]=INF;
    viz[1]=true;
    q.push(1);
    while(!q.empty() && !nc)
    {
        x=q.front();
        q.pop();
        viz[x]=false;
        for(i=0;i<v[x].size();++i)
            if(d[v[x][i].first] > d[x] + v[x][i].second)
            {
                d[v[x][i].first] = d[x] + v[x][i].second;
                if(viz[v[x][i].first]==false)
                {
                    q.push(v[x][i].first);
                    viz[v[x][i].first]=true;
                    ++nri;
                }
                if(nri==n) nc=true;
            }
    }
    if(nc==true) out<<"Ciclu negativ!";
    else
        for(i=2;i<=n;++i) out<<d[i]<<' ';
    return 0;
}