#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

#define maxn 50010
#define inf 0x7fffffff

int n, m;
vector<int> cost, cnt_Q;
//vector<int> tata;
bool negative_cycle;
bitset<maxn> inQ;
vector<vector<pair<int, int>>> graph;

void init()
{
    int i;
    cost[1]=0;
    for(i=2; i<=n; i++)
        cost[i] = inf;
}

void bellmanFord()
{
    queue<int> Q;
    Q.push(1);
    inQ[1] = true;                              //  se afla in Q

    while (!Q.empty() && !negative_cycle){      //  cata vreme Q-ul nu este empty si nu a fost gasit niciun ciclu negativ
        int x = Q.front();
        Q.pop();
        inQ[x] = false;                         //  x nu se mai afla in Q

        for (auto edge : graph[x]) {    //  iterez prin muchiile adiacente lui x

            if(cost[edge.first] > cost[x] + edge.second){       //  daca gasesc un drum mai bun

                cost[edge.first] = cost[x] + edge.second;       //  modific costul minim

                if(inQ[edge.first] == 0) {          //  daca nodul adiacent lui x nu se afla in Q

                    if (cnt_Q[edge.first] > n)      //  daca nodul adiacent lui x a intrat de mai mult de n ori in Q
                        negative_cycle = true;      //  atunci avem de-a face cu un ciclu negativ

                    else {                          //  altfel...
                        inQ[edge.first] = true;     //  introduc nodul in Q
                        Q.push(edge.first);
                        ++cnt_Q[edge.first];        //  prezenta aparitiilor nodului in Q
                    }
                }
            }
        }
    }
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    in >> n >> m;
    graph.resize(n + 1);
    cost.resize(n+1, inf);
    cnt_Q.resize(n+1, 0);
//    tata.resize(n+1, 0);
    cost[1] = 0;

    int x, y, c;
    for(int i=1; i <= m; i++) {
        in >> x >> y >> c;
        graph[x].push_back({y,c});
    }

    init();
    bellmanFord();

    if(negative_cycle){
        out << "Ciclu negativ!\n";
        return 0;
    }
    for(int i=2; i<=n; i++)
        out << cost[i] << ' ';

    in.close();
    out.close();
    return 0;
}