#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define cin fin
#define cout fout

struct el
{
    long long nod, cost;
};

int sursa;
vector<vector<el>> adj;
vector<long long> dist;
queue<int> q;
bool inq[50001];
int viz[50001];


void bellmanford()
{
    dist[sursa] = 0;
    q.push(sursa);
    int n = dist.size() - 1;

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for (auto y:adj[x])
        {
            if (dist[x] + y.cost < dist[y.nod])
            {
                dist[y.nod]=dist[x] + y.cost;

                if (inq[y.nod]) continue;

                q.push(y.nod);
                inq[y.nod]=1;

                viz[y.nod]++;
                if (viz[y.nod] >= n)
                {
                    cout << "Ciclu negativ!";
                    exit(0);
                }

            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    dist.resize(n + 1);
    fill(dist.begin(), dist.end(), 1e18);
    for(int i = 1; i <= m; i++)
    {
        long long x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({y, c});
    }
    sursa = 1;
    bellmanford();
    for(int i = 2; i <= n; i++)
    {
        if(dist[i] == 1e18) cout << 0 << " ";
        else cout << dist[i] << " ";
    }

}