#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define INF 1 << 30

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

    int n, m, x, y, c, i, j;

    in >> n >> m;

    vector<vector<int>> g(n+1);
    vector<vector<int>> w(n+1);

    for (i = 0; i < m; ++i)
    {
        in >> x >> y >> c;
        g[x].push_back(y);
        w[x].push_back(c);
        //out << x << " " << y << ' ' << c << '\n';
    }

    vector<int> dist(n+1);
    vector<int> pr(n+1);

    for (i = 1; i <= n; ++i)
    {
        dist[i] = INF;
        pr[i] = 0;
    }

    dist[1] = 0;

    i = 1;
    while (i < n) {
        for (int u = 1; u <= n; ++u)
        {
            //out << u << ": ";
            for (int v = 0; v < g[u].size(); ++v)
            {
                int weight = w[u][v];
                //out << weight << ' ';
                if (dist[u] + weight < dist[g[u][v]])
                {
                    //out << u << " " << g[u][v] << '\n';
                    dist[g[u][v]] = dist[u] + weight;
                    pr[v] = u;
                }
            }
            //out << '\n';
        }
        ++i;
    }

    for (int u = 1; u <= n; ++u)
    {
        //out << u << ": ";
        for (int v = 0; v < g[u].size(); ++v)
        {
            int weight = w[u][v];

            if (dist[u] + weight < dist[g[u][v]]) {
                /*pr[g[u][v]] = u;
                vector<bool> vis(n+1, false);
                vis[g[u][v]] = true;
                int start = g[u][v];
                while (!visited[start])
                {
                    vis[start] = true;
                    start = pr[start];
                }
                vector <int> ncycle;
                int cycle_start = start;
                ncycle.push_back(u);
                v = pr[u];
                while (start != cycle_start)
                {
                    ncycle.push_back(start);
                    start = pr(start);
                }
                ncycle.push_back(cycle_start);
                */
                out << "Ciclu negativ!";
                return 0;
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        out << dist[i] << ' ';

    in.close();
    out.close();
    return 0;
}