#include <bits/stdc++.h>
#include <queue>

using  namespace std;

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");

#define inf 1000000000
#define NMAX 50001

vector<vector<pair<int, int>>> nums(NMAX);
int viz[NMAX];
int dist[NMAX];

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        nums[x].push_back({y,c});
    }
    
    for(int i = 1; i <= n; i++) dist[i] = inf;

    queue<int> q;
    q.push(1);
    dist[1] = 0;
    bool ok = 1;

    while(!q.empty() && ok == 1)
    {
        int nod = q.front(); q.pop();
        viz[nod]++;

        if(viz[nod] >= n) 
        {
            ok = 0;
            break;
        }

        for(auto x : nums[nod])
        {
            if(dist[nod] + x.second < dist[x.first])
            {
                dist[x.first] = dist[nod] + x.second;
                q.push(x.first);    
            }
        }
        
    }

    if(ok == 0)
    {
        fout << "Ciclu negativ!";
        return 0;
    }

    for(int i = 2; i <= n; i++)
    {
        fout << dist[i] << ' ';
    }

}