#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>

#define inf 2e9

using namespace std;
ifstream in ("bellman.in");
ofstream out ("bellman.out");

struct Node {int x, cost;};

vector<int> BellmanFord(int start, int n, vector<vector<Node>> &listaVecini)
{
    vector<int> d(n, inf);
    vector<int> cnt(n, 0);
    d[start] = 0;
    cnt[start] = 1;


    queue<int> Q;
    Q.push(start);

    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        for (Node v : listaVecini[nod])
        {
            if (d[nod] + v.cost < d[v.x])
            {
                d[v.x] = d[nod] + v.cost;
                Q.push(v.x);
                cnt[v.x] = 1;
                out << "Ciclu negativ!\n";
                return {};

            }
        }
    }

    return d;

}


int main()
{
    int n, m; in >> n >> m;
    vector<vector<Node>> listaVecini(n);

    for (int i = 0; i < m; i++)
    {
        int x, y, cost; in >> x >> y >> cost;
        x--; y--;

        listaVecini[x].emplace_back(y, cost);
        // for directed graphs
        //listaVecini[y].emplace_back(x, cost);
    }

    vector<int> d = BellmanFord(0, n, listaVecini);

    if (d.size() == 0)
        return 0;
    for (int i = 1; i < n; i++)
        out << ((d[i] != inf) ? d[i] : 0) << " ";
    out << "\n";
    return 0;
}