#include <fstream>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
int vec[1000000];
int viz[50010],fr[50010];
int T[3][250010],Start[50010],coada[50010];
int k,nr1,nr2,cost;

///CITIRE
void Citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>nr1>>nr2>>cost;
        k++;
        T[0][k]=nr2;
        T[1][k]=Start[nr1];
        T[2][k]=cost;
        Start[nr1]=k;
    }
    for(int i=2;i<=n;i++)
        coada[i]=300000000;
    vec[1]=1;
}
///CITIRE

///REZOLVARE
void Solve ()
{
    int pi=1,ps=1,st,elem,ok=true;
    while(ps<=pi)
    {
        elem=vec[ps];
        viz[elem]=1;
        st=Start[elem];
        while(st)
        {
            if(coada[elem]+T[2][st]<coada[T[0][st]])
            {
                coada[T[0][st]]=coada[elem]+T[2][st];
                if(coada[1]<0)
                {
                    ok=0;
                    break;
                }
                if(viz[T[0][st]]==0)
                {
                    viz[T[0][st]]=1;
                    vec[++pi]=T[0][st];
                    fr[T[0][st]]++;
                    if(fr[T[0][st]]>m)
                    {
                        ok=0;
                        break;
                    }
                }
            }
            st=T[1][st];
        }
        ps++;
    }
    if(!ok)
        g<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++) g<<coada[i]<<" ";
}
///REZOLVARE

///MAIN
int main()
{
    Citire();
    Solve();
    return 0;
}
///MAIN