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

using namespace std;

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

void bellmanford(int n, const vector<vector<int>> &edges, int alap, vector<int> &dist)
{
    for(int i = 1; i <= n; i++)
    {
        for(vector<int> edge : edges)
        {
            int a = edge[0];
            int b = edge[1];
            int ar = edge[2];

            if(dist[a] != INT_MAX && dist[a] + ar < dist[b])
            {
                if(i == n)
                {
                    ki << "Ciclu negativ!";
                    return;
                }

                dist[b] = dist[a] + ar;
            }
        }
    }

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

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

    vector<vector<int>> edges(m, vector<int>(3));

    for(int i = 0; i < m; i++)
    {
        be >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    vector<int> dist(n + 1, INT_MAX);
    dist[1] = 0;

    bellmanford(n, edges, 1, dist);

    return 0;
}