#include <cstdio>
#include <queue>
#include <vector>
#define INF ~(1<<31)
using namespace std;

struct nod
{
    int vecin,cost;
};

vector <nod> Graf[50010];
queue <int> Coada;
int N,M;
int Prezent[50010];
int Cost[50010];
int Evidenta[50010];

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


int Bellman_Ford()
{
    nod V;
    Coada.push(1);
    Prezent[1]=1;
    Evidenta[1]++;
    while(!Coada.empty())
    {
        int Top=Coada.front();
        Prezent[Top]=0;
        Coada.pop();
        for(int i=0;i<Graf[Top].size();++i)
        {
            V=Graf[Top][i];
            if(Cost[Top]+V.cost<Cost[V.vecin])
            {
                Cost[V.vecin]=Cost[Top]+V.cost;
                Evidenta[V.vecin]++;
                if(!Prezent[V.vecin])
                {
                    Prezent[V.vecin]=1;
                    Coada.push(V.vecin);
                }
                if(Evidenta[V.vecin]>N)
                {
                    printf("Ciclu negativ!");
                    return 1;
                }
            }
        }

    }
    return 0;
}

void Afisare()
{
    for(int i=2;i<=N;++i)
        printf("%d ",Cost[i]);
}



int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    Citire();
    if(!Bellman_Ford())
        Afisare();
    return 0;
}