#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 50001, //MMAX = 250001,
          INF = 1 << 29;

struct muchie
{
    int y, w;
};

int N, M,
    D[NMAX],
    nrViz[NMAX];
vector<muchie> G[NMAX];
queue<int>Q;
bool inQ[NMAX];
ifstream f ( "bellmanford.in" );
ofstream g ( "bellmanford.out" );

void citire()
{
    int x, y, w;
    f >> N >> M;

    for ( int i = 1; i <= M; ++i )
    {
        f >> x >> y >> w;
        G[x].push_back ( {y, w} );
    }
}

void init ( int s )
{
    for ( int i = 1; i <= N; i++ )
        D[i] = INF;

    D[s] = 0;
}

bool BellmanFord ( int src )
{
    int crt, dest, cost;
    init ( src );
    Q.push ( src );
    inQ[src] = 1;

    while ( !Q.empty() )
    {
        crt = Q.front();
        Q.pop();
        inQ[crt] = 0;

        for ( muchie &m : G[crt] )
        {
            cost = D[crt] + m.w;
            dest = m.y;

            if ( cost < D[dest] )
            {
                D[dest] = cost;

                if ( !inQ[dest] )
                {
                    Q.push ( dest );
                    nrViz[dest]++;
                    inQ[dest] = 1;

                    if ( nrViz[dest] >= N )
                        return 0;
                }
            }
        }
    }

    return 1;
}

int main()
{
    citire();

    if ( BellmanFord ( 1 ) )
    {
        for ( int i = 2; i <= N; i++ )
            g << D[i] << ' ';
    }
    else
        g << "Ciclu negativ!";

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