#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define pb push_back
#define nmax 50001
#define inf 0x7fffff
using namespace std;
FILE *f=fopen("bellmanford.in","r"),*g=fopen("bellmanford.out","w");
struct muc{
    long dir,c;
};
vector <muc> l[nmax]; long n,d[nmax],viz[nmax],nr[nmax];
int bellmanford()
{
    long i,j,nod;
    queue <int> q;
    q.push(1);
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        viz[nod]=0;
        for(i=0;i<l[nod].size();i++)
        if(d[l[nod][i].dir]>d[nod]+l[nod][i].c)
        {
            d[l[nod][i].dir]=d[nod]+l[nod][i].c;
            if(viz[l[nod][i].dir]==0)
            {
                viz[l[nod][i].dir]=1;
                q.push(l[nod][i].dir);
                nr[l[nod][i].dir]++;
                if(nr[l[nod][i].dir]>n)
                    return 0;
            }
        }
    }
    return 1;
}
int main()
{
    long m,i,j,x,y; muc aux;
    fscanf(f,"%ld %ld",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%ld %ld %ld",&x,&aux.dir,&aux.c);
        l[x].pb(aux);
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    fclose(f);
    if(!bellmanford())
        fprintf(g,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
        fprintf(g,"%ld ",d[i]);
    fclose(g);
    return 0;
}