#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
#define Nmax 50010
#define INF 999999999
using namespace std;

struct nod
{
    int v,c;
};

vector <nod> Graf[Nmax];
queue <int> C;
int N,M;
int Viz[Nmax];
int P[Nmax];
int Cost[Nmax];

void Citire()
{
    int x;
    nod aux;
    scanf("%d %d",&N,&M);
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d %d",&x,&aux.v,&aux.c);
        Graf[x].push_back(aux);
    }
}

void Rezolvare()
{
    int x;
    nod vec;
    Viz[1]=1;
    P[1]++;
    C.push(1);
    while(!C.empty())
    {
        x=C.front();
        C.pop();
        Viz[x]=0;
        for(int i=0;i<Graf[x].size();++i)
        {
            vec=Graf[x][i];
            if(Cost[vec.v]>Cost[x]+vec.c)
            {
                Cost[vec.v]=Cost[x]+vec.c;
                P[vec.v]++;
                if(!Viz[vec.v])
                {
                    C.push(vec.v);
                    Viz[vec.v]=1;
                }
                if(P[vec.v]==N)
                {
                    printf("Ciclu negativ!");
                    exit(0);
                }
            }
        }
    }
}


int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    Citire();
    for(int i=1;i<=N;++i)
        Cost[i]=INF;
    Cost[1]=0;
    Rezolvare();
    for(int i=2;i<=N;++i)
        printf("%d ",Cost[i]);
    return 0;
}