#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream intrare("bellmanford.in");
ofstream iesire("bellmanford.out");
 
struct muchie
{int x, cost, ord;};

vector<muchie> v[50050];
queue<int> q;
 
int n, m;
int nr[50050];
int vz[50050];
int cmin[50050];

void citeste()
{
    int x, y, cost, i;
    muchie r;
    intrare>>n>>m;
    for (i=1;i<=m;i++)
    {
        intrare>>x>>y>>cost;
        r.cost=cost;
        r.ord=i;
        r.x=y;
        v[x].push_back(r);
    }
    for (i=1; i<=n; i++)
        cmin[i]=2000000000;
}

void bf()
{
    int i, x, sch=0, val;
    muchie r;
    q.push(1);
    cmin[1]=0;
    while (!sch && !q.empty())
    {
        x=q.front();
        q.pop();
        for (i=0; i<v[x].size(); i++)
        {
            r=v[x][i];
            val=cmin[x]+r.cost;
            if (val<cmin[r.x])
            {
                cmin[r.x]=val;
                q.push(r.x);
                nr[r.ord]++;
                if (nr[r.ord]==n)
                {
                    sch=1;
                    break;
                }
            }
        }
    }
    if (sch)
        iesire<<"Ciclu negativ!";
    else
        for (i=2; i<=n; i++)
            iesire<<cmin[i]<< " ";
}

int main()
{
    citeste();
    bf();
    return 0;
}