#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int nmax = 50005;

struct ceva{
    int vec, cost;
};

int n, m, fr[nmax], iq[nmax], a[nmax];
vector<ceva> v[nmax];
queue<int> Q;

void bellman(int nod)
{
    Q.push(nod);
    iq[nod] = fr[nod] = 1;

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

        for(auto x : v[nod])
            if(a[x.vec] > a[nod] + x.cost)
            {
                a[x.vec] = a[nod] + x.cost;
                if(!fr[x.vec])
                    Q.push(x.vec), fr[x.vec] = 1, iq[x.vec] ++;

                if(iq[x.vec] >= n)
                {
                    g << "Ciclu negativ!";
                    exit(0);
                }
            }
    }
}

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

    for(int i = 2; i <= n; i ++)
        a[i] = INT_MAX;

    bellman(1);

    for(int i = 2; i <= n; i ++)
        g << a[i] << " ";
    return 0;
}