#include <bits/stdc++.h>

using namespace std;

#define MAX_N 50000
const int INF = 1e9;

struct node
{
    int a, b;
};

int n, m;
vector <vector <node> > graph;
vector <int> timesInserted, dist;
bitset <MAX_N + 1> inQueue;
queue <int> q;

void bellmanford(int root)
{
    dist[root] = 0;
    timesInserted[root] = 1;
    inQueue[root] = 1;
    q.push(root);

    bool foundCycle = 0;
    while(!q.empty()  &&  !foundCycle)
    {
        int currNode = q.front();
        q.pop();
        inQueue[currNode] = 0;
        for(node x : graph[currNode])
        {
            if(dist[x.a] > dist[currNode] + x.b)
            {
                dist[x.a] = dist[currNode] + x.b;
                if(!inQueue[x.a])
                {
                    q.push(x.a);
                    inQueue[x.a] = 1;
                    timesInserted[x.a] ++;
                    if(timesInserted[x.a] > n)
                        foundCycle = 1;
                }
            }
        }
    }
    if(foundCycle)
    {
        cout << "Ciclu negativ!";
        exit(0);
    }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1);
    dist.resize(n + 1, INF);
    timesInserted.resize(n + 1);

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

    bellmanford(1);

    for(int i = 2; i <= n; i ++)
        cout << dist[i] << " ";
    return 0;
}