#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 50001, //MMAX = 250001,
          INF = 1 << 29;

struct muchie
{
    int x, y, w;
};

int N, M,
    D[NMAX],  ///D[i] = distanta minima de la nodul sursa la i
    nrViz[NMAX];
vector<muchie> G;

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

void citire()
{
    int x, y, w;
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        f >> x >> y >> w;
        G.push_back({x, y, w});
    }
}

void init(int s)
{
    for(int i = 1; i <= N; i++)
        D[i] = INF;
    D[s] = 0;
}

bool BellmanFord(int s)
{
    init(s);
    bool ok = 1; ///Indicator de "relaxare"
    while(ok)
    {
        ok = 0;
        for(muchie &m : G)
            if(D[m.x] < INF)
            {
                int cost = D[m.x] + m.w;
                if(D[m.y] > cost)
                {
                    D[m.y] = cost;
                    ok = 1;  ///s-a efectuat o "relaxare"
                    nrViz[m.y]++;
                    if(nrViz[m.y] >= N)
                        return 0;
                }
            }
    }
    return 1;
}

int main()
{
    citire();
    if(BellmanFord(1))
    {
        for(int i = 2; i <= N; i++)
            g << D[i] << ' ';
    }
    else
        g << "Ciclu negativ!";
    f.close();
    g.close();
    return 0;
}