#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

constexpr int NMAX = 5e4 + 5;
queue <int> Q;
vector <pair<int, int> > G[NMAX];

bool use[NMAX];
bool ciclu_negativ = false;
int lg[NMAX];
int cost[NMAX];

int n, m;
int x, y, c;

int main()
{
	f >> n >> m;

	for (int i=1; i<=m; ++i)
	{
		f >> x >> y >> c;
		G[x].push_back({y, c});
	}

    for (int i=2; i<=n; ++i)
	{
		cost[i] = INF;
		lg[i] = -1;
		use[i] = 0;
	}

	cost[1] = 0;
	lg[1] = 1;
	use[1] = 1;
    Q.push(1);

    while (!Q.empty())
	{
        int nod = Q.front();
        Q.pop();
        use[nod] = 0;

        for (int i=0; i<G[nod].size(); ++i)
		{
            int c = G[nod][i].second;
            int x = G[nod][i].first;

            if (cost[nod] + c < cost[x])
			{
                cost[x] = cost[nod] + c;
                lg[x] = lg[nod] + 1;
                if (lg[x] >= n)
				{
					ciclu_negativ = 1;
					break;
				}
				else if (use[x] == 0)
				{
					Q.push(x);
					use[x] = 1;
				}
			}
		}

		if (ciclu_negativ == 1) break;
	}

    if (ciclu_negativ == 1) g << "Ciclu negativ!" << '\n';
    else
	{
		for (int i=2; i<=n; ++i)
			g << cost[i] << " ";
	}
    return 0;
}