#include <iostream>
#include <fstream>
#define nrn 50001
#define nrm 250001
#define maxi 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int t[3][nrm], viz[nrn], c[nrm*2], start[nrn], cost[nrn],n,m,ok=1,i, cnt[nrn];
void liste_adiacenta()
{
    int i,x,y,z;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        t[0][i]=y;
        t[1][i]=start[x];
        start[x]=i;
        t[2][i]=z;
    }
}
int ford(int nod)
{
    int i,x,y,pi=1, ps=1, k;
    c[pi]=nod;
    for (i=1;i<=n;i++) cost[i]=maxi;
    cost[nod]=0;
    while (ps<=pi)
    {
        k=c[ps];
        x=start[k];
        viz[k]=0;
        while (x)
        {
            if (cost[k]+t[2][x]<cost[t[0][x]])
            {
                cost[t[0][x]]=cost[k]+t[2][x];
                if (!viz[t[0][x]])
                {
                    if (cnt[t[0][x]]>n)
                        return 0;
                    else
                    {
                        c[++pi]=t[0][x];
                        viz[t[0][x]]=1;
                        cnt[t[0][x]]++;
                    }
                }
            }
            x=t[1][x];
        }
        ps++;
    }
    return 1;
}
int main()
{
    f>>n>>m;
    liste_adiacenta();
    ok=ford(1);
    if (!ok) g<<"Ciclu negativ!";
    else
    {
        for (i=2;i<=n;i++)
            g<<cost[i]<<" ";
    }
    return 0;
}