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

using namespace std;

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

const int INF = 0x3f3f3f3f;

int N, M;
int Dmin[50002], nr_ap[50002];
vector<pair<int, int> > V[50002];
queue<int> Q;
bool inQ[50002], cycle;

void bellman_ford()
{
    memset(Dmin, INF, sizeof(Dmin));
    Dmin[1] = 0;
    Q.push(1);
    inQ[1] = true;

    while (!Q.empty() && !cycle)
    {
        int nod = Q.front();
        Q.pop();
        inQ[nod] = false;

        for (vector<pair<int, int> >::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        {
            if (Dmin[nod] + it->second < Dmin[it->first])
            {
                Dmin[it->first] = Dmin[nod] + it->second;
                if (!inQ[it->first])
                {
                    ++nr_ap[it->first];
                    if (nr_ap[it->first] == N)
                    {
                        cycle = true;
                        break;
                    }
                    Q.push(it->first);
                    inQ[it->first] = true;
                }
            }
        }
    }
}

int main ()
{
    fin >> N >> M;
    for (int i = 1, nod1, nod2, cost; i <= M; ++i)
    {
        fin >> nod1 >> nod2 >> cost;
        V[nod1].push_back(make_pair(nod2, cost));
    }

    bellman_ford();


    if (cycle)
        fout << "Ciclu negativ!\n";
    else
    {
        for (int i = 2; i <= N; ++i)
            fout << Dmin[i] << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}