#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
#define INF (1000001)
int n,m,d[50001],v[50001],e;
struct nod
{
    int y,c;
    nod(int y_,int c_)
    {
        y=y_;
        c=c_;
    }
};
vector<nod>la[50001];
queue<nod>bs;
void bellmanford(int S)
{
    d[S]=0;
    for(nod vecin:la[S])
    {
        bs.push(vecin);
        d[vecin.y]=vecin.c;
    }
    while(!bs.empty())
    {
        nod x=bs.front();

        int y=x.y;

        bs.pop();
        v[y]++;
        if(v[y]>n)
        {
            e=1;
            return;
        }
        for(nod vecin:la[y])
        {
            int t=vecin.y,t1=vecin.c;
            if(d[t]>d[y]+t1)
            {
                d[t]=d[y]+t1;
                bs.push(vecin);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    int x,y,z;
    for(int i=1; i<=n; i++)
    {
        d[i]=INF;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        la[x].push_back(nod(y,z));
    }
    bellmanford(1);
    if(e==1)
    {
        cout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2; i<=n; i++)
        {
            cout<<d[i]<<" ";
        }
    }
    return 0;
}