/*

*/

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

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int oo=1000000000;
struct link
{
    int y, cost;
};
int n,m;
vector <link> v[50005];
bool ok,inQ[50005];
int nrQ[50005],d[50005];
queue <int> Q;

void citire()
{
    fin>>n>>m;
    int x;
    link aux;
    for(int i=0;i<m;i++)
    {
        fin>>x>>aux.y>>aux.cost;
        v[x].push_back(aux);
    }
}

void Bellman_Ford()
{
    int nod,vecin,cost;
    ok=1;
    for(int i=2;i<=n;i++)
        d[i]=oo;
    Q.push(1);
    inQ[1]=1;
    nrQ[1]=1;

    while(!Q.empty()&&ok)
    {
        nod=Q.front();
        Q.pop();
        inQ[nod]=0;
        for(int i=0;i<v[nod].size();i++)
        {
            vecin=v[nod][i].y;
            cost=v[nod][i].cost;
            if(d[nod]+cost<d[vecin])
            {
                d[vecin]=d[nod]+cost;
                if(!inQ[vecin])
                {
                    Q.push(vecin);
                    inQ[vecin]=1;
                    nrQ[vecin]++;
                    if(nrQ[vecin]>n)
                    {
                        ok=0;
                        break;
                    }
                }
            }
        }
    }
}

void afisare()
{
    if(ok)
        for(int i=2;i<=n;i++)
            fout<<d[i]<<' ';
    else
        fout<<"Ciclu negativ!";
    fout<<'\n';
}

int main()
{
    citire();
    Bellman_Ford();
    afisare();


    fin.close();
    fout.close();
    return 0;
}