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

#define maxn 50001
#define maxm 250001
#define inf 0x7fffffff

int n, m, i, j, k, cost[maxn], tata[maxn];
bool negative_cycle;
vector<vector<pair<int, int>>> graph;

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

void solve()
{
    queue<int> Q;
    Q.push(1);
    while (!Q.empty()){
        int x = Q.front();
        Q.pop();
        for (auto edge : graph[x]) {
            if(cost[edge.first] > cost[x] + edge.second){
                cost[edge.first] = cost[x] + edge.second;
                tata[edge.first] = x;
                Q.push(edge.first);
            }
        }
    }
}

bool check_negativ()
{
    int i;
    for(i=1; i <= n; ++i) {
        if(!graph[i].empty())
            for (auto x : graph[i]) {
                if (cost[x.first] > cost[i] + x.second)
                    return 1;
            }
    }
    return 0;
}

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

    in >> n >> m;
    graph.resize(n);
    int x, y, c;
    for(i=1; i<=m; i++) {
        in >> x >> y >> c;
        graph[x].push_back({y,c});
    }
    init();
    solve();
    if(check_negativ())
    {
        out << "Ciclu negativ!\n";
        return 0;
    }

    for(i=2; i<=n; i++)
        out << cost[i] << ' ';

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