#include <bits/stdc++.h>

using namespace std;

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

const int dijMax = 50001;
int distanta[dijMax];

class Graf
{
    int NrNoduri;

public:
    Graf(int NrNoduri);
    bool BellmanFord(int nod, vector<pair<int, int>>G[dijMax]);
};

Graf::Graf(int NrNoduri)
{
    this->NrNoduri = NrNoduri;
}

bool Graf :: BellmanFord(int nod, vector<pair<int, int>>G[dijMax])
{
    queue <int> coada;
    int Vizitat[dijMax] = {0};

    for(int i = 1; i <= NrNoduri; i++)
        distanta[i] = INT_MAX;

    distanta[nod] = 0;
    coada.push(nod);
    Vizitat[nod] = 1;

    while(!coada.empty())
    {
        int nodcurent = coada.front();
        Vizitat[nodcurent]++;
        coada.pop();

        if(Vizitat[nodcurent] >= NrNoduri)
            return 0;

        Vizitat[nodcurent] = 0;

        for(int i = 0; i < G[nodcurent].size(); i++)
        {
            int vecin = G[nodcurent][i].first;
            int cost = G[nodcurent][i].second;

            if(distanta[nodcurent] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[nodcurent] + cost;
                if(!Vizitat[vecin])
                    coada.push(vecin);
            }
        }
    }

    return 1;
}


int main()
{
    int N, M;
    int nod1, nod2, cost;
    vector <pair<int, int>>G[dijMax];

    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        in >> nod1 >> nod2 >> cost;
        G[nod1].push_back(make_pair(nod2, cost));
    }

    Graf g(N);
    if(g.BellmanFord(1,G))
    {
        for(int i = 2; i <= N; i++)
            out<<distanta[i]<<" ";
    }
    else
        out<<"Ciclu negativ!";

    return 0;
}