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

using namespace std;

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

struct edge
{
    int to, price;
};

void bellmanford(int n, const vector<vector<edge>> &edges)
{
    vector<int> dist(n + 1, INT_MAX);
    dist[1] = 0;

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

    vector<bool> in(n + 1);
    in[1] = 1;

    vector<int> count(n + 1);

    while(!q.empty())
    {
        int akt = q.front();

        for(edge i : edges[akt])
        {
            int b = i.to;
            int w = i.price;

            if(dist[akt] != INT_MAX && dist[akt] + w < dist[b])
            {
                dist[b] = dist[akt] + w;

                if(!in[b])
                {
                    q.push(b);
                    in[b] = 1;
                    count[b]++;

                    if(count[b] == n - 1)
                    {
                        ki << "Ciclu negativ!";
                        return;
                    }
                }
            }
        }
        q.pop();
        in[akt] = 0;
    }

    for(int i = 2; i <= n; i++)
    {
        ki << dist[i] << " ";
    }
}

int main()
{
    int n, m;
    be >> n >> m;

    vector<vector<edge>> edges(n + 1);

    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        be >> a >> b >> w;

        edges[a].push_back({b, w});
    }

    bellmanford(n, edges);

    return 0;
}