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

ifstream is("bellmanford.in");
ofstream os("bellmanford.out");

int N, M, x, y, z;
int D[50001], Count[50001];
bool B[50001];
vector <pair<int,int> > Graph[50001];
queue <int> Q;

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        Graph[x].push_back(make_pair(y,z));
    }
    for ( int i = 2; i <= N; ++i )
        D[i] = 0x3f3f3f3f;
}

bool BellmanFord()
{
    int node;
    Q.push(1);
    D[1] = 0;
    Count[1] = 1;
    while ( !Q.empty() )
    {
        node = Q.front();
        Q.pop();
        B[node] = 0;
        for ( const auto& v : Graph[node] )
        {
            if ( D[v.first] > D[node] + v.second && !B[v.first] )
            {
                if ( Count[v.first] > N )
                    return 0;
                D[v.first] = D[node] + v.second;
                Q.push(v.first);
                B[v.first] = 1;
                Count[v.first]++;
            }
            if ( D[v.first] > D[node] + v.second && B[v.first] )
                D[v.first] = D[node] + v.second;

        }
    }
    return 1;
}

int main()
{
    Input();
    if ( BellmanFord() )
    {
        for ( int i = 2; i <= N; ++i )
            os << D[i] <<  " ";
    }
    else
        os << "Ciclu negativ!";

    is.close();
    os.close();
}