#include <bits/stdc++.h>
#define NMax 250005
#define NMax2 50005
#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;
queue <int> C;
bool ciclu_negativ;


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


    vector <bool> adaugat(N + 1, 0);
    vector <int> dist(N + 1, inf);
    vector <int> viz(N + 1, 0);

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



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


        for(int i = 0; i < muchii[nod_curent].size(); ++i)
        {
            int y = muchii[nod_curent][i].second;   // nodul destinatie
            int cost = muchii[nod_curent][i].first; // costul de la nodul curent la nodul destinatie

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

                viz[y] ++;

                if(viz[y] >= N) // formeaza cilcu negativ
                {
                    ciclu_negativ = 1;
                    break;
                }

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

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


int main()
{
    //Read();
    Bellman_Ford(1);
    return 0;
}