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

using namespace std;

vector< pair<int,int> > v[maxn+5];
int c[1000000], a[maxn+5], d[maxn+5], nr[maxn+5];

int main(){
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m;
    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;
    int p = 1, u = 1;
    c[1] = 1;
    d[1] = 0;
    nr[1] = 1;
    int num = 1;
    
    while (p <= u && cod == 1){
        nod = c[p];
        p++;
        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]++; 
                    u++;
                    c[u] = pr.first;
                    if (nr[pr.first] == n){
                        cod = 0;
                        break;
                    }
                }    
            }   
        }   
    }
    
    if (cod == 0)
        g<<"Ciclu negativ!";
    else 
        for (i = 2; i <= n; i++)
            g<<d[i]<<endl;
        
    return 0;
}