#include <cstdio>
#include <vector>
#include <deque>

using namespace std;
FILE *f,*g;

struct name
{
    int ve,c;
};
vector <name> v[50002];
deque <int> coada;
int d[50002];
bool viz[50003];
int fr[50003],ci,n;

void bf(int nod)
{
    coada.push_back(nod);
    viz[nod]=1;
    fr[nod]=1;
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop_front();
        viz[nod]=0;
        for(int i=0;i<v[nod].size();++i)
        {
            if(d[v[nod][i].ve]>d[nod]+v[nod][i].c)
            {
                d[v[nod][i].ve]=d[nod]+v[nod][i].c;
                if(!viz[v[nod][i].ve])
                {
                    viz[v[nod][i].ve]=1;
                    if(++fr[v[nod][i].ve]>n)
                    {
                        ci=1;
                        fprintf(g,"Ciclu negativ!");
                        return;
                    }
                    coada.push_back(v[nod][i].ve);
                }
            }
        }
    }
}
int main()
{
    f=fopen("bellmanford.in","r");
    g=fopen("bellmanford.out","w");
    int m,x,y,z;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    for(int i=1;i<=n;++i)
        d[i]=1999999999;
    d[1]=0;
    bf(1);
    if(!ci)
        for(int i=2;i<=n;++i)
            fprintf(g,"%d ",d[i]);
    fclose(f);
    fclose(g);
    return 0;
}