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

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, INF);
    vector<int> pr(n+1, -1);
    vector<bool> inqueue(n, false);

    dist[1] = 0;
    inqueue[1] = true;

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

    vector<int> visits(n+1, 0);

    i = 1;
    while (!q.empty()) {
        int st = 1;

        int u = q.front();
        q.pop();
        inqueue[u] = false;

        visits[u]++;
        if (visits[u] >= n)
        {
            out << "Ciclu negativ!";
            return 0;
        }

            //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[g[u][v]] = u;

                    if (!inqueue[g[u][v]])
                    {
                        q.push(g[u][v]);
                        inqueue[g[u][v]] = true;
                    }
                }
            }
            //out << '\n';
        ++i;
        ++st;
    }

    /*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;
}