#include <cstdio>
#include <queue>
#define INF 99999999

using namespace std;

int n,m;
int cost[50001],viz[50001];
struct nod{int inf,cost; nod *urm;} *g[50001];
queue <int> Q;

void baga(int x, int y, int c)
{
    nod *q=new nod;
    q->inf=y;
    q->cost=c;
    q->urm=g[x];
    g[x]=q;
}

void ciclu_negativ()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        if(cost[x]+c<cost[y])
        {
            printf("Ciclu negativ!\n");
            return;
        }
    }
    for(int i=2;i<=n;i++)
        printf("%d ",cost[i]);
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        baga(x,y,c);
    }
    for(int i=2;i<=n;i++)
        cost[i]=INF;
    viz[1]=1;
    Q.push(1);
    long long nr=0;
    while(!Q.empty() && nr<=(long long) n*m)
    {
        nr++;
        x=Q.front();
        viz[x]=0;
        for(nod *q=g[x];q;q=q->urm)
            if(cost[q->inf]>cost[x]+q->cost)
            {
                cost[q->inf]=cost[x]+q->cost;
                if(!viz[q->inf])
                {
                    viz[q->inf]=1;
                    Q.push(q->inf);
                }
            }
        Q.pop();
    }
    ciclu_negativ();
    fclose(stdout);
    return 0;
}