#include <bits/stdc++.h>
#define Nmax 50005
#define mp make_pair
using namespace std;

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

typedef pair < int, pair < int, int > > pi;

vector < pi > v;

int d[Nmax];

const int INF = 10000005;
int n, m;

void read ( );
void Bellman_Ford ( );

bool check_ciclu_negativ ( )
{
    vector < pi > :: iterator it;

    for ( it = v.begin(); it != v.end(); it++ )
         if ( d[it->second.second] > d[ it->second.first] + it->first )
            return 1;

    return 0;
}

int main ( )
{
    read ( );

    Bellman_Ford ( );

    if ( check_ciclu_negativ( ) )
        fout << "Ciclu negativ!";
    else
        for ( int i = 2; i <= n; i++ )
        fout << d[i] << ' ' ;
}

void Bellman_Ford ( )
{
    vector < pi > :: iterator it;

    for ( int i = 2; i <= n; i++ )
        d[i] = INF;

    for ( int i = 1; i < n; i++ )
    {
        for ( it = v.begin(); it != v.end(); it++ )
        {
            if ( d[it->second.second] > d[ it->second.first] + it->first )
                d[it->second.second] = d[ it->second.first] + it->first;
        }
    }
}

void read ( )
{
    int x, y, c;

    fin >> n >> m;

    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y >> c;

        v.push_back ( mp( c, mp( x, y ) ) );
    }
}