#include <bits/stdc++.h>

using namespace std;


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

const int MAX=50001;
int n,m,st,dr,cost,x,y,c;
int d[MAX];

vector<pair<int,int> >graf[MAX];

void bellmanford(int start)
{
    for(int i=1;i<=n;i++) d[i]=1000*1000*1000;
    queue<int>q;

    d[start]=0;

    q.push(start);

    long long max_op=n*(long long)m/2;

    while(!q.empty() && max_op>=0)
    {
        max_op--;
        x=q.front();
        q.pop();
        for(int i=0;i<graf[x].size();i++)
        {
            pair<int,int> p=graf[x][i];
            y=p.first;
            c=p.second;
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                q.push(y);
            }
        }
    }
}

int a[250005];
int b[250005];
int co[250005];

int main()
{
    in>>n>>m;


    for(int i=1;i<=m;i++)
    {
        in>>st>>dr>>cost;
        graf[st].push_back(make_pair(dr,cost));
        a[i]=st;
        b[i]=dr;
        co[i]=cost;
    }

    bellmanford(1);

    for(int i=1;i<=m;i++)
    {
        if(d[a[i]]+co[i]<d[b[i]])
        {
            out<<"Ciclu negativ!\n";
            return 0;
        }
    }

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

    return 0;
}