#include <fstream>
#include <vector>
#include <iostream>
#define NMAX 50003
#include <queue>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector <int>v[NMAX],d[NMAX];
queue <int>q;

int n,m,a,b,c,s[NMAX],ok=1;
int ap[NMAX];
void Bell(int k)
{
    q.push(k);
    while(!q.empty()&&ok)
    {
        int nod=q.front();
        q.pop();
        if(ap[nod]==n)ok=0;
        int nr=v[nod].size();
        for(int i=0;i<nr;++i)
        {
            int u=v[nod][i];
            if((ap[u]==0)||(s[u]>s[nod]+d[nod][i]))
            {
                s[u]=s[nod]+d[nod][i];
                q.push(u);
                ap[u]++;
            }
        }
    }
}
int main()
{
    f>>n>>m;ap[1]=1;
    for(int i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        d[a].push_back(c);
    }
    Bell(1);
    if(ok)
    for(int i=2;i<=n;++i)g<<s[i]<<" ";
    else g<<"Ciclu negativ!";
    return 0;
}