#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

using PI = pair<int, int>;
using VI = vector<int>;

vector<vector<PI>> G;

const int DIM = 50010, INF = 0x3f3f3f3f;
VI D, cnt;
int n, m;

void ReadGraph();
void BellmanFord(int x, VI& D);

int main()
{
    ReadGraph();

	BellmanFord(1, D);

    for (int i = 2; i <= n; i++)
        fout << D[i] << " ";

    return 0;
}

void BellmanFord(int x, VI& D)
{
	queue<int> Q;
	bitset<DIM> inQ;

	D = VI(n + 1, INF);
	D[x] = 0;
	Q.push(x);
    inQ[x] = 1;

    while ( !Q.empty() )
    {
        x = Q.front();
        Q.pop();
        inQ[x] = 0;
        for (auto& [y, w] : G[x])
            if (D[y] > D[x] + w)
            {
                D[y] = D[x] + w;

                if (!inQ[y])
                {
                    Q.push(y);
                    inQ[y] = 1;
                }

                cnt[y]++;
				if (cnt[y] == n)
				{
					fout << "Ciclu negativ!";
					exit(0);
				}
            }
    }
}

void ReadGraph()
{
	int x, y, w;
	fin >> n >> m;

	G = vector<vector<PI>>(n + 1);
	cnt = VI(n + 1);

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