#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,t[3][250001],start[50001],cost[50001],C[1000000],viz[50001],fr[50001];
bool ok=1;
void citire()
{
    int i,k=0,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        k++;
        f>>x>>y>>t[2][k];
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
}
void initializare()
{
    for(int i=2;i<=n;i++)
         cost[i]=999999;
}
void bellmanford()
{
    int ps=1,pi=1,x,vecin;
    viz[1]=1;
    C[pi]=1;
    cost[1]=0;
    while(ps<=pi)
    {
        x=C[ps];
        fr[x]++;
        if(fr[x]>=n)///daca trec la infinit prin nodul x
        {
            ok=0;
            break;
        }
        vecin=start[x];
        while(vecin)///cat timp mai avem vecini
        {
            if(cost[x]+t[2][vecin]<cost[t[0][vecin]])///daca se imbunatateste costul
            {
                cost[t[0][vecin]]=cost[x]+t[2][vecin];///actualizez costul
                if(viz[t[0][vecin]]==0)
                {
                    viz[t[0][vecin]]=1;///vizitez vecinul
                    C[++pi]=t[0][vecin];///si il adaug in coada
                }
            }
            vecin=t[1][vecin];///trec la urmatorul vecin
        }
        viz[x]=0;///ma prefac ca nu l-am vizitat
        ps++;
    }
}
int main()
{
    citire();
    initializare();
    bellmanford();
    if(ok==0)
        g<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            g<<cost[i]<<" ";
    return 0;
}