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

using namespace std;

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

#define INF 10000000

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

void bellman_ford(int node)
{
    bool inQueue[edge_nr + 1] = { false };
    for (int i = 0; i <= nodes; i++)
    {
        dist[i] = INF;
    }
    dist[node] = 0;
 
    queue<int> q;
    q.push(node);
    inQueue[node] = true;
 
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        for(auto e : edges)
        {
            int aux, v, weight;
            tie(aux, v, weight) = e;
 
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
 
    // Print the result
    bool changes = false;

    for(auto e : edges)
    {
        int a, b, w;
        tie(a, b, w) = e;
        if(dist[b] > dist[a] + w)
        {
            changes = true;
            break;
        }
    }

    if(changes)
        fout << "Ciclu negativ!";
    else
    {
        for(int i = 2; i <= nodes; i++)
        {
            fout << dist[i] << ' ';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int 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;
}