#include <fstream>
#include <vector>
using namespace std;

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

int n, m;
const int INF = 999999999;

struct muchie{
    int vf, cost;
};

vector<muchie> v[50100];

int d[50100], s[50100], q[1000000], first = 0, last = -1, nrori[50100];
bool inq[50100];

void q_push(int x)
{
    last++;
    q[last] = x;
    inq[x] = 1;
    nrori[x]++;
}
int q_pop()
{
    inq[q[first]] = 0;
    return q[first++];
}
bool q_empty()
{
    return first > last;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        muchie aux;
        aux.cost = c;
        aux.vf = y;
        v[x].push_back(aux);
    }
    int init = 1;
    for(int i = 0; i <= n + 1; i++)
    {
        d[i] = INF;
    }
    d[init] = 0;
    q_push(init);
    while(!q_empty())
    {
        int vf = q_pop();
        for(int x = 0; x < v[vf].size(); x++)
        {
            if(d[vf] + v[vf][x].cost < d[v[vf][x].vf])
            {
                d[v[vf][x].vf] = d[vf] + v[vf][x].cost;
                if(inq[v[vf][x].vf] == 0)
                {
                    q_push(v[vf][x].vf);
                    if(nrori[v[vf][x].vf] == n)
                    {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i = 2; i <= n; i++)
    {
        fout << d[i] << ' ';
    }


    return 0;
}