#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

struct nod {int i, c;};

vector <nod> *v;
vector <int> cntq, cost;
vector <bool> inq;
queue <int> q;

int n, m, i, x, y, c, s;
bool ciclu_neg = false;

int main()
{
    ifstream fin("bellmanford.in");

    fin >> n >> m;
    cntq.resize(n+1, 0);
    cost.resize(n+1, 0x7fffffff);
    inq.resize(n+1, false);
    v = new vector <nod> [n+1];
    
    for(i = 1; i<=m; ++i)
    {
        nod y;
        fin >> x >> y.i >> y.c;
        v[x].push_back(y);
    }
    
    q.push(1);
    cost[1] = 0;
    inq[1] = true;
    
    while(!q.empty() && !ciclu_neg)
    {
        x = q.front();
        q.pop();
        inq[x] = false;
        
        s = v[x].size();
        
        for(i = 0; i<s; ++i)
        {
            y = v[x][i].i, c = v[x][i].c;
            
            if(cost[x] + c < cost[y])
            {
                cost[y] = cost[x] + c;
                
                if(!inq[y])
                {
                    if(cntq[y] > n)
                        ciclu_neg = true;
                    else
                    {
                        q.push(y);
                        inq[y] = true;
                        cntq[y] ++;
                    }
                }
                
            }
        }
    }
    
    delete[] v;
    fin.close();
    
    ofstream fout("bellmanford.out");
    
    if(ciclu_neg)
        fout << "Ciclu negativ!";
    else
    {
        for(i = 2; i<=n; ++i)
            fout << cost[i] << ' ';
    }

    fout.close();
    
    return 0;
}