#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#define nmax 50000
#define inf (1<<30)
using namespace std;


void get_data(vector <pair<int, int> > edges[nmax], int &Nedges, int &Nnodes)
{
    ifstream fin ("bellmanford.in");
    fin >> Nnodes >> Nedges;
    for (int i = 0; i < Nedges; i++)
    {
        int nodeX, nodeY, weight;
        fin >> nodeX >> nodeY >> weight;
        edges[nodeX].push_back(make_pair(nodeY, weight));
    }
}


bool BellmanFord(vector <pair<int,int> > edges[nmax], int Nedges, int Nnodes, int dist[nmax])
{
    queue <int> q;
    q.push(1);
    int cycle[nmax];
    for (int i = 1; i <= Nnodes; i++)
        cycle[i] = 0;
    while(!q.empty())
    {
        int current = q.front();
        cycle[current] ++;
        if (cycle[current] == Nnodes)
            return true;
        q.pop();
        int current_dist = dist[current];
        for (auto neigh: edges[current])
        {
            int neigh_dist = neigh.second;
            if (dist[neigh.first] > current_dist + neigh_dist)
            {
                dist[neigh.first] = current_dist + neigh_dist;
                q.push(neigh.first);

            }
        }
    }
    return false;
}

int main()
{
    vector <pair<int, int> > edges[nmax];
    int dist[nmax];
    int Nedges, Nnodes;

    get_data(edges, Nedges, Nnodes);
    for (int i = 2; i <= Nnodes; i++)
        dist[i] = inf;
    ofstream fout ("bellmanford.out");
    if (BellmanFord(edges, Nedges, Nnodes, dist))
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= Nnodes; i++)
            fout << dist[i] << " ";
    return 0;
}