#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define inf 2e9
#define Nmax 50001
using namespace std;

ofstream g("bellmanford.out");

int n,m,mn[Nmax],lg,viz[Nmax],nr[Nmax];

struct edge{
    int nod,val,nr,ant;
};
vector<edge> V[Nmax];
vector<edge> C;


bool comp(edge a,edge b)
{
    return a.val>b.val;
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);

    for (int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        edge crt;
        crt.val = c;
        crt.nod = y;
        crt.nr = i;
        V[x].push_back(crt);
        crt.nod = x;
        V[y].push_back(crt);
    }

    for (int i=1;i<=n;i++)
        mn[i] = -inf;

    edge crt;
    crt.nod = 1;
    crt.val = 0;
    crt.nr = 0;
    crt.ant = -1;
    C.push_back(crt);
    while (!C.empty())
    {
        crt = C[0];
        nr[crt.nr]++;
        viz[crt.nod] = 1;
        mn[crt.nod] = crt.val;
        pop_heap(C.begin(),C.end(),comp);
        C.pop_back();
        for (int j=0;j<V[crt.nod].size();j++)
        {
            if (nr[V[crt.nod][j].nr]>=n && viz[V[crt.nod][j].nod] && mn[V[crt.nod][j].nod]>mn[crt.nod] + V[crt.nod][j].val)
            {
                g<<"Ciclu negativ!";
                return 0;
            }
            if (V[crt.nod][j].nod != crt.ant && (!viz[V[crt.nod][j].nod] || mn[V[crt.nod][j].nod]>mn[crt.nod] + V[crt.nod][j].val))
            {
                edge crt2;
                crt2 = V[crt.nod][j];
                crt2.val+=crt.val;
                crt2.ant = crt.nod;
                C.push_back(crt2);
                push_heap(C.begin(),C.end(),comp);
            }
        }
    }

    for (int i=2;i<=n;i++)
        g<<mn[i]<<' ';

    return 0;
}