#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n,m;
vector <pair<int,int> > G[50002];
vector <pair<int,int> > ::iterator IT;
queue <pair<int,int> > BF;
int vDist[50002],vT[50002];
void citire()
{
    scanf("%d%d",&n,&m);
    int aux1,aux2,aux3;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&aux1,&aux2,&aux3);
        G[aux1].push_back(make_pair(aux2,aux3));
    }
}
void init()
{
    for(int i=2; i<=n; i++)
        vDist[i]=0x3f3f3f3f;
}
bool bellmanFord()
{
    init();
    vT[1]=1;
    BF.push(make_pair(1,0));
    int nod,dist;
    while(!BF.empty())
    {
        nod=BF.front().first;
        dist=BF.front().second;
        BF.pop();
        for(IT=G[nod].begin(); IT!=G[nod].end(); IT++)
        {
            if((dist+IT->second)<vDist[IT->first])
            {
                vDist[IT->first]=(dist+IT->second);
                vT[IT->first]++;

                if(vT[IT->first]>n)
                    return false;

                BF.push(make_pair(IT->first,IT->second));
            }
        }
    }
    return true;
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    if(bellmanFord())
        for(int i=2; i<=n; i++)
            printf("%d ",vDist[i]);
    else
        printf("Ciclu negativ!");
    return 0;
}