#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

typedef struct { int x,c; } node;

struct cmp_node
{
    bool operator () (node x,node y)
    {
        return x.c > y.c;
    }
};

node make_node(int x,int c)
{
    node now;
    now.x = x;
    now.c = c;
    return now;
}

typedef priority_queue<node,vector<node>,cmp_node> MinH;

ifstream F("bellmanford.in");
ofstream G("bellmanford.out");

const int Nmax = 50010;

int N,M,D[Nmax],T[Nmax];
vector<node> V[Nmax];

#define IT(type) vector<type>::iterator

bool ciclu_negativ = false;

void Bellman_pq(int start)
{
    MinH Q;

    D[start] = 0;
    Q.push( make_node(start,D[start]) );

    while ( Q.size() )
    {
        while ( D[Q.top().x] != Q.top().c )
        {
            Q.pop();
            if ( Q.empty() ) break;
        }
        if ( Q.empty() ) break;

        node now = Q.top();
        Q.pop();

        for (IT(node) it=V[now.x].begin();it!=V[now.x].end();++it)
            if ( D[it->x] > D[now.x] + it->c )
            {
                if ( ++T[it->x] == N )
                {
                    ciclu_negativ = 1;
                    return;
                }
                D[it->x] = D[now.x] + it->c;
                Q.push( make_node( it->x , D[now.x] + it->c ) );
            }
    }
}

void Bellman(int start)
{
    queue<node> Q;

    D[start] = 0;
    Q.push( make_node(start,D[start]) );

    while ( Q.size() )
    {
        while ( D[Q.front().x] != Q.front().c )
        {
            Q.pop();
            if ( Q.empty() ) break;
        }
        if ( Q.empty() ) break;

        node now = Q.front();
        Q.pop();

        for (IT(node) it=V[now.x].begin();it!=V[now.x].end();++it)
            if ( D[it->x] > D[now.x] + it->c )
            {
                if ( ++T[it->x] == N )
                {
                    ciclu_negativ = 1;
                    return;
                }
                D[it->x] = D[now.x] + it->c;
                Q.push( make_node( it->x , D[now.x] + it->c ) );
            }
    }
}

int main()
{
    F>>N>>M;
    memset(D,0x3f,sizeof(D));
    for (int i=1,x,y,c;i<=M;++i)
    {
        F>>x>>y>>c;
        V[ x ].push_back( make_node( y,c ) );
    }

    Bellman_pq(1);
    //Bellman(1);

    if ( ciclu_negativ )
    {
        G<<"Ciclu negativ!\n";
        return 0;
    }

    for (int i=1;i<=N;++i)
        if ( i != 1 )
        {
            int out = D[i] == D[0] ? 0 : D[i];
            G<<out<<' ';
        }
    G<<'\n';
}