#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>

#define N_MAX 50001

using namespace std;

int main()
{
    int m,n,i,nod,nod_n,cost,distanta[N_MAX],repetitii[N_MAX];
    vector < pair < int,int > > muchii[N_MAX];
    queue < int > que;

    ifstream f("bellmanford.in");

    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>nod>>nod_n>>cost;
        --nod;
        --nod_n;
        muchii[nod].push_back(make_pair(nod_n, cost));
    }
    f.close();

    que.push(0);

    for(i = 0; i < n; ++i)
    {
        distanta[i] = INT_MAX;
        repetitii[i] = 0;
    }
    distanta[0] = 0;

    ofstream g("bellmanford.out");
    while(!que.empty())
    {
        nod = que.front();
        que.pop();

        m = muchii[nod].size();
        for(i = 0; i < m; ++ i)
        {
            nod_n = muchii[nod][i].first;
            cost = muchii[nod][i].second;

            if(distanta[nod_n] > distanta[nod] + cost)
            {
                distanta[nod_n] = distanta[nod] + cost;
                que.push(nod_n);

                ++repetitii[nod];
            }
        }

        if(repetitii[nod] > n)
        {
            g<<"Ciclu negativ!";
            g.close();
            return 0;
        }
    }

    for(i = 1; i < n; ++i)
        if(distanta[i] == INT_MAX)
            g<<"0 ";
        else
            g<<distanta[i]<<" ";
    g.close();

    return 0;
}