#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
#include <climits>

#define ll long long
#define pb push_back

using namespace std;

 ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NLIM = 5e4 + 10;

int N, M;
vector< int > graph[NLIM];
vector< int > cost[NLIM];
vector< int > nr[NLIM];

int dist[NLIM];

int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        int x, y, l;
        fin >> x >> y >> l;
        graph[x].push_back( y );
        cost[x].push_back( l );
        nr[x].push_back( 0 );
    }
    for( int i = 1; i <= N; ++i )
        dist[i] = INT_MAX;


    queue< int > qu;
    dist[1] = 0;
    qu.push( 1 );

    while( qu.size() )
    {

        int nod = qu.front();
        for( int j = 0; j < graph[nod].size(); ++j )
        {

            int nnod = graph[nod][j];
            int hcost = cost[nod][j];
            if( dist[nod] + hcost < dist[nnod] )
            {
                dist[nnod] = dist[nod] + hcost;


                ++nr[nod][j];
                if( nr[nod][j] > N - 1 )
                {
                    fout << "Ciclu negativ!";
                    return 0;
                }
//cout << "wat";
                qu.push( nnod );
            }
        }
        qu.pop();
    }


    for( int i = 2; i <= N; ++i )
    {
        fout << dist[i] << " ";
    }

    return 0;
}