#include <bits/stdc++.h>

using namespace std;

#define NMAX 50005
#define MMAX 250005

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

int n,m;
struct muchie{
    int v;
    int cost;
};
vector<muchie> graf[NMAX];
int32_t dist[NMAX];
queue<int> q;
bitset<NMAX> inQ;

bool cicluNegativ()
{
    for(int i=1;i<=n;i++)
    {
        for(auto x:graf[i])
        {
            int vecin=x.v;
            int cost=x.cost;
            if(dist[vecin]>dist[i]+cost)
                return true;
        }
    }
    return false;
}

void bellman()
{
    q.push(1);
    inQ[1]=1;
    dist[1]=0;

    for(int32_t i=0;q.size()&&1<=1LL*n*m;i++)
    {
        int nod=q.front();
        inQ[nod]=0;
        q.pop();

        for(auto x:graf[nod])
        {
            int vecin=x.v;
            int cost=x.cost;

            if(dist[vecin]>dist[nod]+cost)
            {
                dist[vecin]=dist[nod]+cost;
                if(!inQ[vecin])
                {
                    inQ[vecin]=1;
                    q.push(vecin);
                }
            }
        }
    }

    if(cicluNegativ())
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<' ';
    }
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf[x].push_back({y,z});
    }
    fill(dist,dist+n+1,LONG_MAX);
    bellman();
    return 0;
}