// BellmanFord.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <vector>
#include <fstream>
#include <tuple>

using namespace std;

const int MAX_N = 50000 + 1;
const int MAX_M = 250000 + 1;
const int oo = static_cast<int>(1e9);


vector<tuple<int, int, int>> edges;
int N, M;
int s;

vector<int> d(MAX_N);


void INITIALIZE_SINGLE_SOURCE()
{
    for (int i = 1; i <= N; ++i)
    {
        d[i] = oo;
    }

    d[s] = 0;
}


void RELAX(int u, int v, int weight)
{
    if (d[u] + weight < d[v])
    {
        d[v] = d[u] + weight;
    }
}


bool BELLMAN_FORD()
{
    INITIALIZE_SINGLE_SOURCE();


    for (int i = 1; i <= N - 1; ++i)
    {
        for (auto& e : edges)
        {
            int u = get<0>(e);
            int v = get<1>(e);
            int weight = get<2>(e);

            RELAX(u, v, weight);
        }
    }

    
    for (auto& e : edges)
    {
        int u = get<0>(e);
        int v = get<1>(e);
        int weight = get<2>(e);

        if (d[u] + weight < d[v])
        {
            return false;
        }
    }

    return true;
}


int main()
{
    ifstream fin{ "bellmanford.in" };
    ofstream fout{ "bellmanford.out" };

    s = 1;

    fin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int u, v, weight;

        fin >> u >> v >> weight;

        edges.push_back({ u, v, weight });
    }



    bool ok = BELLMAN_FORD();

    if (ok == false)
    {
        fout << "Ciclu negativ!" << endl;
    }
    else
    {
        for (int i = 2; i <= N; ++i)
        {
            fout << d[i] << " ";
        }

        fout << endl;
    }

    return 0;
}