#include <fstream>

using namespace std;

struct list{
int u,v,c;
}l[250001];

int dist[50001],pr[50001];

int main()
{   int i,j,n,m,ok=0;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    dist[1]=0;
    for(i=2;i<=n;i++) dist[i]=2100000000;
    for(i=1;i<=m;i++)
    {
        f>>l[i].u>>l[i].v>>l[i].c;
    }

    for(i=1;i<=n-1;i++)
    {
     for(j=1;j<=m;j++)
     {
         if(dist[l[i].u]+l[i].c<dist[l[i].v])
         {
             dist[l[i].v]=dist[l[i].u]+l[i].c;
             pr[l[i].v]=l[i].u;
         }
     }
    }

    for(j=1;j<=m;j++)
     {
         if(dist[l[i].u]+l[i].c<dist[l[i].v])
         {
             dist[l[i].v]=dist[l[i].u]+l[i].c;
             pr[l[i].v]=l[i].u;
             ok=1;
             break;
         }
     }
    if(ok) {g<<"Ciclu negativ!"; return 0;}


    for(i=2;i<=n;i++) g<<dist[i]<<' ';
    g<<'\n';
    //for(i=1;i<=n;i++) g<<pr[i]<<' ';
    //g<<'\n';


    f.close();
    g.close();
    return 0;
}