#include <iostream>
#include <vector>
#include <fstream>
#include <tuple>
#include <string.h>

using namespace std;

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

#define INF 10000000

int nodes;
vector < tuple<int, int, int> > edges;
int dist[100000];

void bellman_ford(int node)
{
    bool changes;
    for(int i = 0; i <= nodes; i++)
    {
        dist[i] = INF;
    }
    dist[node] = 0;
    for(int i = 0; i < nodes; i++)
    {
        if(changes == false)
            break;
        changes = false;
        for(auto e : edges)
        {
            int a, b, w;
            tie(a, b, w) = e;
            if(dist[b] > dist[a] + w){
                dist[b] = dist[a] + w;
                changes = true;
            }
        }
    }
    if(changes)
        fout << "Ciclu negativ!";
    else
    {
        for(int i = 2; i <= nodes; i++)
        {
            fout << dist[i] << ' ';
        }
    }
}

int main()
{
    int edge_nr, a, b, w;
    fin >> nodes >> edge_nr;
    for(int i = 0; i < edge_nr; i++)
    {
        fin >> a >> b >> w;
        edges.push_back(make_tuple(a, b, w));
    }
    bellman_ford(1);

    return 0;
}