#include <bits/stdc++.h>
#define NMax 250001
#define NMax2 50001
#define inf 2e9

using namespace std;

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


// nr noduri, nr muchii, perechile de muchii si costul asociat
int N, M;
vector <pair<int, int>> muchii[NMax];

int dist[NMax2], viz[NMax2];
queue <int> C;
bool adaugat[NMax2];



void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        muchii[x].push_back({cost,y});
    }
}


bool Bellman_Ford(int s)
{
    for(int i = 1; i <= N; ++i)
        viz[i] = 0, adaugat[i] = 0, dist[i] = inf;

    dist[s] = 0;
    C.push(s);
    adaugat[s] = 1;

    while(!C.empty())
    {
        int nod_curent = C.front();
        C.pop();
        adaugat[nod_curent] = 0;
        viz[nod_curent] ++;

        if(viz[nod_curent] >= N)
            return -1;

        for(auto i : muchii[nod_curent])
        {
            int y = i.second;
            int cost = i.first;

            if(dist[nod_curent] + cost < dist[y])
            {
                dist[y] = dist[nod_curent] + cost;

                if(!adaugat[y])
                    C.push(y);
            }
        }
    }
    return 1;
}


int main()
{
    Read();

    if(Bellman_Ford(1))
    {
        for(int i = 2; i <= N; ++i)
            fout << dist[i] << " ";
    }
    else
        fout << "Ciclu negativ!";

    return 0;
}