#include <fstream>
#include <vector>
#define inf 0x7fffffff
#define msj "Ciclu negativ!"
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int lim=5e4+3;
int dist[lim];
struct Op
{
    int x;
    int y;
    int c;
};
vector<Op> edge;
int main()
{
    int n,m,src,dest,cost;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>src>>dest>>cost;
        edge.push_back({src,dest,cost});
    }
    for(int i=2;i<=n;++i)
        dist[i]=inf;
    dist[1]=0;
    for(int w=1;w<n;++w)
    for(auto e:edge)
    if(dist[e.x]!=inf and dist[e.y]>dist[e.x]+e.c)
        dist[e.y]=dist[e.x]+e.c;
    for(auto e:edge)
    if(dist[e.x]!=inf and dist[e.y]>dist[e.x]+e.c)
    {
        cout<<msj;
        return 0;
    }
    for(int i=2;i<=n;++i)
        cout<<dist[i]<<' ';
    return 0;
}