#include <bits/stdc++.h>
#define oo 2000000001
using namespace std;

/**
*/
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
       ///   nod, cost
vector <pair <int,int> >L[50002];
int viz[50002]; /// viz[i]=1 daca nodul i este pus in coada
int n, d[50002]; /// d[i] = costul minim pana la nodul i
int contor[50002]; /// numar de cate ori am pus nodul i
                   /// in coada
queue<int> q;

void Citire()
{

}

void BellmanFord()
{
    bool existaNegative;
    int i,x,c,w;
    /// initializari:
    for (i=2;i<=n;i++)
        d[i]=oo;
    existaNegative=false;
    viz[1]=1;
    q.push(1);
    contor[1]=1;
    while (!q.empty() && !existaNegative)
    {
        x=q.front();
        q.pop();
        viz[x]=0;
        for (w=0;w<L[x].size();w++)
        {
            i=L[x][w].first;
            c=L[x][w].second;
            if (d[i]>d[x]+c)
            {
                d[i]=d[x]+c;
                if (viz[i]==0)
                {
                    if (contor[i]>n) existaNegative=true;
                    else
                    {
                        q.push(i);
                        viz[i]=1;
                        contor[i]++;
                    }
                }
            }
        }
    }
    if (existaNegative) g<<"Ciclu negativ!\n";
    else
    {
        for (i=2;i<=n;i++)
            g<<d[i]<<" ";
        g<<"\n";
    }
}

int main()
{
    int i,x,y,c,m;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        L[x].push_back({y, c});
    }
    BellmanFord();
    f.close();
    g.close();
    return 0;
}