#include <fstream>

#define nMax 50001
#define INF 1000000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m;
int distanta[nMax], frecv[nMax];
bool viz[nMax];

struct lista
{
    int val, dist;
    lista *nxt;
};

lista *heads[nMax]={NULL};

void insertFront(lista * &hd, int v, int d)
{
    lista *elem=new lista;
    elem->val=v;
    elem->dist=d;
    elem->nxt=hd;
    hd=elem;
}

struct coada
{
    int val;
    coada *nxt;
};

int main()
{
    int a, b, c;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        insertFront(heads[a], b, c);
    }

    for(int i=2; i<=n; i++)
        distanta[i]=INF;

    coada *cap=new coada;
    cap->val=1;
    cap->nxt=NULL;

    coada *lst=new coada;
    lst=cap;

    while(cap!=NULL)
    {
        int node=cap->val;
        viz[node]=0;
        lista *nod=heads[node];
        while(nod!=NULL)
        {
            int fiu=nod->val, dd=nod->dist;
            if(distanta[node]+dd<distanta[fiu])
            {
                distanta[fiu]=distanta[node]+dd;
                frecv[fiu]++;
                if(viz[fiu]==0)
                {
                    viz[fiu]=1;
                    coada *newFiu=new coada;
                    newFiu->val=fiu;
                    newFiu->nxt=NULL;
                    lst->nxt=newFiu;
                    lst=newFiu;
                }
                if(frecv[fiu]>=n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
            }
            nod=nod->nxt;
        }
        cap=cap->nxt;
    }
    for(int i=2; i<=n; i++)
        fout<<distanta[i]<<" ";
}