/*#include <fstream>
#define NMAX 50002
#define INF 1000000000
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,start,neg;
struct arc
{
    int vf,c;
};
arc G[NMAX][NMAX];
int g[NMAX];
int C[NMAX*NMAX];
int inc,sf;
int d[NMAX];
int nr[NMAX];
void citire();
void bellman_ford();
void afisare();
int main()
{
    citire();
    bellman_ford();
    afisare();
    return 0;
}
void citire()
{
    int i;
    arc a;
    int x, y, cost;
    start=1;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        ///y intra in lista de adiacenta a lui x
        a.vf=y;
        a.c=cost;
        G[x][g[x]++]=a;
    }
}
void bellman_ford()
{
    int i,x,y,c;
    for(i=1; i<=n; i++)
        d[i]=INF;
    d[start]=0;
    C[0]=start;
    inc=sf=0;
    while(inc<=sf && !neg)
    {
        x=C[inc++];
        ///parcurg lista de adiacengta a lui x
        for(i=0; i<=g[x]; i++)
        {
            y=G[x][i].vf;
            c=G[x][i].c;
            if(d[y]>d[x]+c)
            {
                d[y]=d[x]+c;
                nr[y]++;
                if(nr[y]>n)
                {
                    neg=1;
                    break;
                }
                C[++sf]=y;
            }

        }
    }
}
void afisare()
{
    int i;
    if(neg)
        fout<<"Ciclu negativ!";
    else
        for(i=2; i<=n; i++)
            if(d[i]==INF)
                fout<<-1<<' ';
            else
                fout<<d[i]<<' ';
}
*/
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 100000000
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,start,neg;
struct arc
{
    int vf,c;
};
vector <arc> G[NMAX];
queue <int> C;

int d[NMAX];
int nr[NMAX];
void citire();
void bellman_ford();
void afisare();
int main()
{
    citire();
    bellman_ford();
    afisare();
    return 0;
}
void citire()
{
    int i;
    arc a;
    int x, y, cost;
    start=1;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        ///y intra in lista de adiacenta a lui x
        a.vf=y;
        a.c=cost;
        G[x].push_back(a);
    }
}
void bellman_ford()
{
    int i,x,y,c;
    for(i=1; i<=n; i++)
        d[i]=INF;
    d[start]=0;
    C.push(start);

    while(!C.empty() && !neg)
    {
        x=C.front();
        C.pop();
        ///parcurg lista de adiacengta a lui x
        for(i=0; i<G[x].size(); i++)
        {
            y=G[x][i].vf;
            c=G[x][i].c;
            if(d[y]>d[x]+c)
            {
                d[y]=d[x]+c;
                nr[y]++;
                if(nr[y]>n)
                {
                    neg=1;
                    break;
                }
                C.push(y);
            }

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