#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

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

#define INF 0x3f3f3f3f
#define Gmax 50010


int dist[Gmax];
int V,E;

struct Edgeul
{
    int from =123;
    int to = 123;
    int cost = 123;
}Edge[Gmax];

int main()
{
    f>>V>>E;

    for(int i=0; i<E; i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        Edge[i].from = x;
        Edge[i].to = y;
        Edge[i].cost = c;
/*
        Edge[i].from = y;
        Edge[i].to = x;
        Edge[i].cost = c;
        */

    }
    memset(dist, 0x3f, sizeof(dist));

    dist[1] = 0;
    for(int i=0; i<V-1;i++)
    {
        for(int j=0;j<E;j++)
        {
            if(dist[Edge[j].from] + Edge[j].cost < dist[Edge[j].to])
                dist[Edge[j].to] = dist[Edge[j].from] + Edge[j].cost;
        }
    }

    for(int i=0; i<V-1;i++)
    {
        for(int j=0;j<E;j++)
        {
            if(dist[Edge[j].from] + Edge[j].cost < dist[Edge[j].to])
                dist[Edge[j].to] = -INF;
        }
    }
    bool negative = false;
    for(int i=2; i<=V; i++)
    {
         if(dist[i]==-INF)
         {
            g<<"Ciclu negativ!";
            negative = true;
            break;
         }

    }
    if(!negative)
   {
        for(int i=2; i<=V; i++)
        {
            if(dist[i]==INF) g<<0<<' ';
            else
                g<<dist[i] <<' ';
        }
    }


    return 0;
}