#include <fstream>
#include <vector>
#include <queue>

using namespace std;
using edge = pair<int, int>;

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

static constexpr int nMAX = ((int)(5e4) + 4),
                     INF = ((int)(1e9));

static constexpr int source = (1);

int n;
vector<edge> G[nMAX];

void add_edge(const int u, const int v, const int w)
{
    G[u].push_back({w, v});
    return;
}

void read()
{
    int m = 0;
    f >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u = 0, v = 0, w = 0;
        f >> u >> v >> w;

        add_edge(u, v, w);
    }

    return;
}

int main()
{
    read();

    vector<int> d((n + 1), INF), in_queue((n + 1), false), counts((n + 1), false);

    queue<int> Q = {};

    d[source] = 0, in_queue[source] = true, counts[source] = 1, Q.push(source);

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

        in_queue[node] = false;

        for (const edge &e : G[node])
            if ((d[node] + e.first) < d[e.second])
            {
                d[e.second] = (d[node] + e.first);

                if (in_queue[e.second])
                    continue;

                if ((++counts[e.second]) >= n)
                {
                    g << "Ciclu negativ!\n";
                    exit(0);
                }

                Q.push(e.second), in_queue[e.second] = 1;
            }
    }

    for (int i = 2; i <= n; ++i)
    {
        g << ((d[i] == INF) ? 0 : d[i]);

        if (i == n)
            g << '\n';
        else
            g << ' ';
    }

    return 0;
}