#include <stdio.h>

#include <queue>//lenea asta
#include <vector>

using namespace std;

struct edge;

struct node
{
    int id;
    vector<edge> n;//neightbours
};

struct edge
{
    int cost;
    node *v;
};

#define MAX_N 50000
#define INF 0x3fffffff

char inQ[MAX_N];
int times[MAX_N];
int dist[MAX_N];
node graph[MAX_N];

int main()
{
    FILE *fin = fopen("bellmanford.in", "r"),
         *fout = fopen("bellmanford.out", "w");
    queue<node*> q;
    int n, m;

    fscanf(fin, "%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int u, v, cost;
        edge e;

        fscanf(fin, "%d %d %d", &u, &v, &cost);

        e.cost = cost;
        e.v = &graph[v - 1];
        graph[u - 1].n.push_back(e);
    }

    int start = 0;
    for(int i = 0; i < n; i++)
        dist[i] = INF, graph[i].id = i;
    dist[start] = 0;

    q.push(&graph[start]);
    inQ[start] = 1;
    times[start]++;
    while(!q.empty() && times[q.front()->id])
    {
        node *x = q.front();
        int n_neighbours = x->n.size();
        q.pop();

        inQ[x->id] = 0;

        for(int i = 0; i < n_neighbours; i++)
        {
            edge it = x->n[i];
            if(dist[it.v->id] > dist[x->id] + it.cost)
            {
               dist[it.v->id] = dist[x->id] + it.cost;
                if(!inQ[it.v->id])
                {
                    q.push(it.v);
                    inQ[it.v->id];
                    times[it.v->id]++;
                }
            }
        }
    }

    if(!q.empty())
        fprintf(fout, "Ciclu negativ!");
    else
        for(int i = 1; i < n; i++)
        {
            if(dist[i] == INF)
                dist[i] = 0;
            fprintf(fout, "%d ", dist[i]);
        }

    fclose(fin);
    fclose(fout);
    return 0;
}