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

int varfuri, muchii, D[50005], viz[50005];
bool inCoada[50005];
vector<pair<int, int>>graf[50005];
vector<int>v;
queue<int>qu;

bool BellmanFord(int varf)
{
    D[varf] = 0;
    qu.push(varf);
    inCoada[varf] = true;

    while(!qu.empty())
    {
        int nodCurent = qu.front();
        ++viz[nodCurent];
        if (viz[nodCurent] >= varfuri)
            return false;
        qu.pop();
        inCoada[nodCurent] = false;

        for (unsigned int i = 0; i < graf[nodCurent].size(); ++i)
        {
            int vecin = graf[nodCurent][i].first;
            int cost = graf[nodCurent][i].second;
            if (D[nodCurent] + cost < D[vecin])
            {
                D[vecin] = D[nodCurent] + cost;
                if (!inCoada[vecin])
                    qu.push(vecin);
            }
        }
    }
    return true;
}
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin >> varfuri >> muchii;
    for (int i = 1; i <= muchii; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back(make_pair(y, c));
    }
    for (int i = 1; i <= varfuri; ++i)
        D[i] = 1 << 30;

    if (BellmanFord(1))
        for (int i = 2; i<= varfuri; ++i)
            fout<<D[i]<<" ";
    else
        fout<<"Ciclu negativ!";
}