#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, cost[maxn], tata[maxn], cnt_Q[maxn];
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].flip();
    while (!Q.empty() && !negative_cycle){
        int x = Q.front();
        Q.pop();
        inQ[x] = false;
        for (auto edge : graph[x]) {
            if(cost[edge.first] > cost[x] + edge.second){
                cost[edge.first] = cost[x] + edge.second;
                if(inQ[edge.first] == 0) {
                    if (cnt_Q[edge.first] > n)
                        negative_cycle = true;
                    else {
                        inQ[edge.first] = true;
                        Q.push(edge.first);
                        ++cnt_Q[edge.first];
                    }
                }
            }
        }
    }
}

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

    in >> n >> m;
    graph.resize(n + 1);

    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;
}