#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50007
#define INF 123123123
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
struct varf
{
    int x,c;
};
vector<varf>G[NMAX];
int n,start=1,m;
int cmin[NMAX];
int nr[NMAX];
bool cicluneg;
queue<int> C;
void citire();
void bellmanford();
void afisare();
int main()
{
    citire();
    bellmanford();
    afisare();
    return 0;
}
void citire()
{
    int x,y,cost;
    varf vf;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        cin>>x>>y>>cost;
        vf.x=y;
        vf.c=cost;
        G[x].push_back(vf);
       /* vf.x=x;
        G[y].push_back(vf);*/
    }
}

void bellmanford()
{
    int i,k,vfmin,cost,x;

    pair<int,int> p;
    for(i=1; i<=n; i++)
    {
        cmin[i]=INF;
    }
    cmin[start]=0;
    C.push(start);
    while(!C.empty() && !cicluneg)
    {
        x=C.front();
        C.pop();
        for(i=0; i<G[x].size(); i++)
        {
            if(cmin[G[x][i].x]>cmin[x]+G[x][i].c)
            {
                cmin[G[x][i].x]=cmin[x]+G[x][i].c;
                nr[G[x][i].x]++;
                if( nr[G[x][i].x]==n) cicluneg=1;
                C.push(G[x][i].x);
            }
        }
    }

}
void afisare()
{
    int i;
    if(cicluneg)
        cout<<"Ciclu negativ!";
    else
    {
        for(i=2; i<=n; i++) cout<<cmin[i]<<" ";
    }
}