#include <bits/stdc++.h>
using std::ifstream;
using std::ofstream;
using std::vector;
using std::queue;
using std::cout;
ifstream fin ( "bellmanford.in" );
ofstream fout( "bellmanford.out" );
constexpr int NMAX = 50002;
constexpr int VMAX = 250002;
constexpr int INFINITE = 9999999;

int distance[NMAX], optimiz[NMAX];
struct arc { int dst, cost; };
vector<arc> g[NMAX];
int n, m;

void onnegativecycle()
{
    fout << "Ciclu negativ!";
    exit(0);
}

void bellmanford()
{
    // step 1: Initialize
    for (int i = 1; i <= n; i++)
    {
        distance[i] = INFINITE;
        // predecessor[i] = 0;
    }

    distance[1] = 0;

    queue<int> q;
    q.push(1);

    while (!q.empty())
    {
        int qf = q.front();
        q.pop();

        for (const arc& nd : g[qf])
        {
            if (distance[nd.dst] > distance[qf] + nd.cost)
            {
                distance[nd.dst] = distance[qf] + nd.cost;
                optimiz[nd.dst]++;
                if (optimiz[nd.dst] > n)
                    onnegativecycle();
                q.push(nd.dst);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({ b, c });
    }

    bellmanford();

    for (int i = 2; i <= n; i++)
    {
        fout << distance[i] << ' ';
    }

    return 0;
}