#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define INF 1294967296
#define NMax 50002
using namespace std;
vector< pair<int,int> > G[NMax];
int dmin[NMax],nr[NMax];
int n,x0=1;
bool negativ=false;
void read()
{
    int i,m,x,y,c;
        freopen("bellmanford.in","r",stdin);
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            G[x].push_back(make_pair(y,c));
        }
        fclose(stdin);
}
void bellman()
{
    int i,from;
    vector< pair<int,int> >::iterator it;
    queue<int> q;
    for(i=1;i<=n;i++) dmin[i]=INF;
    dmin[x0]=0;
    q.push(x0);
    while(!q.empty() && !negativ)
    {
        from=q.front();
        q.pop();
       for(it=G[from].begin();it!=G[from].end();it++)
        {
            if(dmin[it->first] > dmin[from]+ it->second)
            {
             dmin[it->first]=dmin[from]+ it->second;
             nr[it->first]++;
             q.push(it->first);
            }
            if(nr[it->first]>n) negativ=true;
        }
    }
}
void afisare()
{
    int i;
    freopen("bellmanford.out","w",stdout);
    if(negativ)
    {
        printf("Ciclu negativ!");
    }
    else
    {
        for(i=2;i<=n;i++)
        {
            printf("%d ",dmin[i]);
        }
    }
    fclose(stdout);
}
int main()
{
    read();
    bellman();
    afisare();
    return 0;
}