//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000000
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

vector < pair <int, int> > g[50500];
queue <int> q;
int n,m,i,j,x,y,dis,nr[50500],viz[50500],sem,d[50500],k;
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>dis;
        g[x].push_back({y,dis});
    }
    d[1]=0;
    for(i=2; i<=n; i++)
        d[i]=inf;
    q.push(1);
    nr[1]++;
    viz[1]=1;
    sem=0;
    while(!q.empty() && sem==0)
    {
        k=q.front();
        q.pop();
        viz[k]=0;
        for(auto j:g[k])
        {
            i=j.first;
            dis=j.second;
            if(d[k]+dis<d[i])
            {
                d[i]=d[k]+dis;
                if(viz[i]==0)
                {
                    if(nr[i]>n) sem=1;
                    else
                    {
                        q.push(i);
                        viz[i]=1;
                        nr[i]++;
                    }
                }

            }

        }

    }
    if(sem==1) cout<<"Ciclu negativ!"<<'\n';
    else
        for(i=2;i<=n;i++)
        {
            if(d[i]==2000000000) cout<<"0 ";
            else cout<<d[i]<<" ";
        }

    return 0;
}