#include <bits/stdc++.h>
#define N_MAX 50005
#define INF 1e9

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct edge
{
    int x, y, c;
};

int n, m, x, y, c;
vector < edge > E;
int dist[N_MAX];

bool BellmanFord()
{
    for (int i = 1; i < n; i++)
    {
        for (edge e: E)
        {
            dist[e.y] = min(dist[e.y], dist[e.x] + e.c);
        }
    }

    for (edge e: E)
        if (dist[e.y] > dist[e.x] + e.c)
            return false;
    return true;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        E.push_back({x, y, c});
    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;

    if (!BellmanFord())
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (int i = 2; i <= n; i++)
        fout << dist[i] << " ";
    return 0;
}