#include <bits/stdc++.h>
#include <limits>

using namespace std;

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

int infinit = std::numeric_limits<int>::max();
vector<pair<int,int>> costuri[100001];
int V[100001], dist[100001];

void update(int u, int v, int cost)
{
    dist[v] = min(dist[v], dist[u] + cost);
}

void bellmanford(int nr_N, int& ok)
{
    ok = 0; ///Verific daca am ciclu sau nu
    dist[1]=0;

    priority_queue<pair<int,int>> H; /// Va sorta singur in functie de cea mai mica distanta
    H.push({0,1});

    while(H.size() > 0)
    {

        int u = H.top().second;
        H.pop();
        V[u]++;

        if (V[u] >= nr_N)               /// Daca ciclul da un numar negativ se va invartii in jurul acelui cilcu la infinit
        {
            ok = 1;
            out << "Ciclu negativ!";
            break;
        }
        else
        {
            ///cout << u << ": ";
            for(auto v : costuri[u]) /// Verificam toti vecinii lui u
            {
                if(dist[v.first] > dist[u] + v.second)
                {
                    dist[v.first] = dist[u] + v.second;
                    H.push({-dist[v.first], v.first}); /// Folosim -dist[v.first] ca sa avem in top cea mai mica valoare
                    ///cout << v.first << ", " << dist[v.first] << " || ";
                }
            }
            ///cout << V[u];
            ///cout << endl;
        }
    }
}

int main()
{
    int nr_N, nr_M, ok = 0;
    in >> nr_N >> nr_M;

    for(int i = 1; i <= nr_M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        costuri[x].push_back({y,c}); /// Muchia de la x plecand in y are costul c
    }

    for(int i = 1; i <= nr_N; i++)
        dist[i] = infinit;

    bellmanford(nr_N, ok);

    if(ok == 0)
    {
        for(int i = 2; i <= nr_N; i++)
        {
            if(dist[i] != infinit)
                out << dist[i] << " ";
        }
    }
    return 0;
}