#include <cstdio>
#include <vector>
#include <queue>
#define NR 500000000

using namespace std;

struct pereche
{
    int nod,val;
};

vector <pereche> muchii[50001];
queue <int> Q;

int distante[50001],in_coada[50001];
bool in_coada1[50001];

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=m;++i)
    {
        if (i>1 && i<=n)
            distante[i]=NR;
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        muchii[a].push_back({b,c});
    }
    Q.push(1);
    bool a=1;
    while (Q.empty()==0 && a)
    {
        int x=Q.front();
        Q.pop();
        in_coada1[x]=0;
        int l=muchii[x].size();
        for (int i=0;i<l;++i)
        {
            if (distante[muchii[x][i].nod]==NR || distante[muchii[x][i].nod]>distante[x]+muchii[x][i].val)
            {
                distante[muchii[x][i].nod]=distante[x]+muchii[x][i].val;
                if (!in_coada1[muchii[x][i].nod])
                {
                    Q.push(muchii[x][i].nod);
                    in_coada1[muchii[x][i].nod]=1;
                    in_coada[muchii[x][i].nod]++;
                    if (in_coada[muchii[x][i].nod]>n) a=0;
                }
            }
        }
    }
    if (a==0) printf("Ciclu negativ!");
    else for (int i=2;i<=n;++i)
        if (distante[i]==NR) printf("0 ");
        else printf("%d ",distante[i]);
}