#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
const int maxx=50005;
const int pinf=1<<29;
typedef pair<int, int> per;

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

int n, m, ok, i, d[maxx], t[maxx], fv[maxx];
bool v[maxx];
vector<per> g[maxx];
queue<int> q;

void citire(vector<per>g[], int &n, int &m)
{
    int x, y, c, i;
    fi >> n >> m;
    for(i=1 ; i<=m ; i++)
    {
        fi >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
}

void Bellman(vector<per>g[], int n, int d[], int t[])
{
    int i, j, z;
    vector<per>::iterator it;
    for(i=1 ; i<=n ; i++)
    {
        d[i]=pinf;
        t[i]=0;
        v[i]=false;
    }
    d[1]=0;
    v[1]=true;
    q.push(1);
    ok=1;
    while(!q.empty() && ok == 1)
    {
        z=q.front();
        v[z]=false;
        fv[z]++;
        if(fv[z] > n)
            ok=0;
        for(it=g[z].begin() ; it!=g[z].end() ; it++)
        {
            if(d[z] + it->second < d[it->first])
            {
                d[it->first]=d[z]+it->second;
                t[it->first]=z;
                if(!v[it->first])
                {
                    q.push(it->first);
                    v[it->first]=true;
                }
            }
        }
        q.pop();
    }
}

int main()
{
    citire(g, n, m);
    Bellman(g, n, d, t);
    if(ok == 1)
    {
        for(i=2 ; i<=n ; i++)
            fo << d[i] << " ";
    }
    else
        fo << "Ciclu negativ!";
    return 0;
}