#include <fstream>
#include <vector>
#include <list>
#include <queue>
#define inf 100000
#define nmax 50005

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int  n, m, x, y, sol, s, v, k, c, l;
int a[500005], ciclu[nmax], d[nmax];
queue<int> q;
vector<int> G[nmax], C[nmax];

int bellmanfordBFS(int x)
{
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    d[x] = 0;
    q.push(x);

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

        ciclu[x]++;
        if (ciclu[x] > n)
            return -1;
        for(int i=0; i<G[x].size(); ++i)
            if (d[G[x][i]] > d[x] + C[x][i]) {
                d[G[x][i]] = d[x] + C[x][i];
                q.push(G[x][i]);
            }
        q.pop();
    }
    return 1;

}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        G[x].push_back(y);
        C[x].push_back(c);
    }
    int c = bellmanfordBFS(1);
    if (c > 0)
    {
        for (int i = 2; i <= n; i++)
            g << d[i] << " ";
    }
    else g << "Ciclu negativ!";

    return 0;
}