#include <cstdio>
#include <queue>
using namespace std;
const int inf=9<<30;

int n,m,ciclunegativ=0,d[50001];
unsigned short inlista[50001],nrintrariinlista[50001];

struct graf
{
    int v,c;
    graf* u;
}*a[50001];

void read()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x;
    graf *nod;
    for(int i=0;i<m;++i)
    {
        scanf("%d",&x);
        nod=new graf;
        nod->u=a[x];
        a[x]=nod;
        scanf("%d",&x);
        nod->v=x;
        scanf("%d",&x);
        nod->c=x;
    }
}

void init()
{
    d[1]=0;
    ++n;
    for(int i=2;i<n;++i)
    {
        d[i]=inf;
    }
   /* k=1;
    lista[0]=1;
    inlista[1]=1;
    ++nrintrariinlista[1];
    graf *nod=a[1];
    k=0;
    while(nod)
    {
        d[nod->v]=nod->c;

        inlista[nod->v]=1;
        ++nrintrariinlista[nod->v];
        nod=nod->u;
    }*/
}

void bellmanford()
{
    int i;
    graf* nod;
    queue <unsigned short> c;
    c.push(1);
    while(!c.empty())
    {
        i=c.front();
        c.pop();
        inlista[i]=0;
        nod=a[i];
        while(nod)
        {
            if(d[nod->v]>d[i]+nod->c)
            {
                d[nod->v]=d[i]+nod->c;
                if(!inlista[nod->v])
                {
                    if(++nrintrariinlista[nod->v]>n-2)
                    {
                        ciclunegativ=1;
                        return;
                    }
                    c.push(nod->v);
                    inlista[nod->v]=1;
                }
            }
            nod=nod->u;
        }
    }
}

/*int negativ()
{
    graf *nod;
    for(int i=1;i<n;++i)
    {
        nod=a[i];
        while(nod)
        {
            if(d[i]+nod->c<d[nod->v]) return 1;
            nod=nod->u;
        }
    }
    return 0;
}*/

void scrie()
{
    freopen("bellmanford.out","w",stdout);
    if(ciclunegativ) printf("Ciclu negativ!");
    else for(int i=2;i<n;++i) printf("%d ",d[i]);
    printf("\n");
}

int main()
{
    read();
    init();
    bellmanford();
    scrie();
    return 0;
}