#include <iostream>
#include<fstream>
#include<queue>
#define inf 1000000000
#define mp make_pair
#define f first
#define s second
using namespace std;
ifstream f("bellmanford.in");
ofstream gout("bellmanford.out");
int n,m,i,cst,v[50001],j,k,x,y,nod,ct[250001];
vector<int>q;
vector<pair<int,int> >g[50001];
bool ok,e[50001];
struct muchie
{
    int x,y;
};
muchie c[250001];
int functie(int i,int j,int c)
{
    if(v[j]>v[i]+c)
    {
        v[j]=v[i]+c;
        return 1;
    }
    return 0;
}
void sterge(int j)
{
    swap(q[j],q[q.size()-1]);
    q.pop_back();
}
int main()
{
    f>>n>>m;
    q.push_back(0);
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>cst;
        g[x].push_back(mp(y,cst));
        c[i].x=x;
        c[i].y=y;
        ct[i]=cst;
    }
    v[1]=0;
    for(i=2; i<=n; i++)
        v[i]=inf;
    q.push_back(1);
    e[1]=1;
    int sw=1;
    for(i=1;i<n;i++)
    {
        sw=0;
        for(j=1; j<q.size(); j++)
        {
            nod=q[j];
            for(k=0; k<g[nod].size(); k++)
                if(functie(nod,g[nod][k].f,g[nod][k].s))
                {
                    if(!e[g[nod][k].f])
                        q.push_back(g[nod][k].f),e[g[nod][k].f]=1;
                }
            sterge(j);
            e[nod]=0;
        }
    }
    ok=1;
    for(j=1; j<=m && ok; j++)
    {
        if(functie(c[j].x,c[j].y,ct[j]))
        {
            ok=0;
            gout<<"Ciclu negativ!";
        }
    }
    if(ok)
        for(i=2; i<=n; i++)
            gout<<v[i]<<' ';
}