#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#define NMax 50005
#define INF 1<<29
using namespace std;
std::vector< std::pair<int,int> > G[NMax];
std::queue< std::pair<int,int> > coada;
int n,m,x,y,c,d[NMax],nodes[NMax];
bool viz[NMax];
bool BellmanFord(int x0)
{
    for(int i=1;i<=n;++i)d[i] = INF;
    d[x0] = 0;
    viz[x0] = true;
    coada.push( std::make_pair(x0,0) );
    while(!coada.empty())
    {
        int nod = (coada.front()).first;
        int val = (coada.front()).second;
        coada.pop();
        for(int i=0;i<G[nod].size();++i)
        {
            if(d[G[nod][i].first] > G[nod][i].second+val)
            {
                ++nodes[nod];
                if(nodes[nod]>n)return false;
                d[G[nod][i].first] = G[nod][i].second+val;
                coada.push( std::make_pair(G[nod][i].first,d[G[nod][i].first]) );
            }
        }
    }
    return true;
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back( std::make_pair(y,c) );
    }
    if(!BellmanFord(1))printf("Ciclu negativ!");
    else
    {
        for(int i=2;i<=n;++i)printf("%d ",d[i]);
    }
    return 0;
}