#include <fstream>
#include <vector>
#include <iostream>
#include <queue>
#include <bitset>

using namespace std;

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

const int NMax = 50000, oo = 2e9;

struct str{int x, c;};

vector <str> G[NMax + 5];

int N, M, DP[NMax + 5], NrRelax[NMax + 5];

bitset <NMax + 5> InQ;

queue <int> Q;

void Read()
{
    fin >> N >> M;

    for(int i = 0, x, y, c; i < M; i++)
    {
        fin >> x >> y >> c;

        G[x].push_back({y, c});
    }
}

bool BellmanFord()
{
    Q.push(1), InQ[1] = true;

    while(!Q.empty())
    {
        int Nod = Q.front(); Q.pop(), InQ[Nod] = false;

        for(auto K : G[Nod])
        {
            int Vecin = K.x, cost = K.c;

            if(DP[Vecin] > DP[Nod] + cost)
            {
                DP[Vecin] = DP[Nod] + cost, NrRelax[Vecin]++;

                if(NrRelax[Vecin] > N)
                    return 0;

                if(!InQ[Vecin])
                    Q.push(Vecin), InQ[Vecin] = true;
            }
        }
    }
    return 1;
}

void Print()
{
    for(int i = 2; i <= N; i++)
        fout << DP[i] << " ";

    fout << '\n';
}

int main()
{
    Read();

    for(int i = 2; i <= N; i++) DP[i] = oo;

    if(!BellmanFord())
        fout << "Ciclu negativ!\n";
    else
        Print();

    fin.close();
    fout.close();

    return 0;
}