#include<vector>
#include<fstream>
#define maxn 50000
#define lmax 500000000

using namespace std;

vector< pair<int,int> > v[maxn+5];
int h[maxn+2], a[maxn+5], d[maxn+5], pos[maxn+5], nr[maxn+5], lh;

void up(int k){
    int x = h[k];
    while (k > 1 && d[h[k/2]] > d[x]) {
        h[k] = h[k/2];
        pos[h[k]] = k;
        k = k/2;
    }
    h[k] = x;
    pos[x] = k;   
}

void down(int k){
    int son = 1, aux;
    while (son != 0){
        son = 0;
        if (k*2 <= lh){
            son = k*2;
            if (k*2+1 <= lh && d[h[k*2]] > d[h[k*2+1]])
                son = k*2+1;
            if (son != 0 && d[h[son]] > d[h[k]])
                son = 0;
        }
        if (son != 0){
            aux = h[son];
            h[son] = h[k];
            h[k] = aux;
            pos[h[k]] = k;
            pos[h[son]] = son;
            k = son;     
        }
    }    
}

int main(){
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m, poz;
    f>>n>>m;
    int i, j, k, dist, nod;
    int x, y;
    pair<int,int> pr;
    for (i = 1; i <= m; i++){
        f>>x>>y>>dist;
        v[x].push_back(make_pair(y, dist));
    }
    
    for (i = 2; i <= n; i++)
        d[i] = lmax;
    
    int cod = 1;
    h[1] = 1;
    d[1] = 0;
    pos[1] = 1;
    nr[1] = 1;
    lh = 1;
    
    while (lh > 0 && cod == 1){
        nod = h[1];
        h[1] = h[lh];
        lh--;
        down(1);
        a[nod] = 0; 
        for (i = 0; i < v[nod].size(); i++){
            pr = v[nod][i]; 
            if (d[pr.first] > d[nod] + pr.second){
                d[pr.first] = d[nod] + pr.second; 
                if (a[pr.first] == 0){
                    a[pr.first] = 1;
                    nr[pr.first]++; 
                    if (nr[pr.first] == n){
                        cod = 0;
                        break;
                    }
                    lh++;
                    h[lh] = pr.first;
                    pos[pr.first] = lh;
                    poz = lh;
                } 
                else 
                    poz = pos[pr.first];
                up(poz);
            }   
        }   
    }
    
    if (cod == 0)
        g<<"Ciclu negativ!";
    else 
        for (i = 2; i <= n; i++)
            g<<d[i]<<" ";
        
    return 0;
}