#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

const int NMAX = 50005;
const int INF = (1e9);

vector < pair<int, int> > G[NMAX];
int viz[NMAX], dist[NMAX];
bool inCoada[NMAX];
int n, m;
int negativ;
queue <int> Q;

void bellmanford()
{
    dist[1] = 0;
    Q.push(1);
    inCoada[1] = 1;
    //viz[1]++;

    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        inCoada[curr] = 0;
        viz[curr]++;

        if (viz[curr] > n)
        {
            negativ = 1;
            return;
        }

        for (auto v: G[curr])
        {
            if (dist[curr] + v.second < dist[v.first])
            {
                dist[v.first] = dist[curr] + v.second;
                if (!inCoada[v.first])
                {
                    inCoada[v.first] = 1;
                    Q.push(v.first);
                }
            }
        }
    }
}

int main()
{
    fi >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        fi >> u >> v >> c;
        G[u].pb({v, c});
    }

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

    if (negativ)
        fo << "Ciclu negativ!";
    else
    {
        for (int i = 2; i <= n; i++)
            fo << dist[i] << " ";
    }

    return 0;
}