#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, int  > pi;

vector < pi > v[Nmax];
bitset < Nmax > b;

int d[Nmax], cnt[Nmax];

const int INF = 10000005;
int n, m;

void read ( );
bool Bellman_Ford ( );

int main ( )
{
    read ( );

    if ( Bellman_Ford ( ) == 1 )
    for ( int i = 2; i <= n; i++ )
    fout << d[i] << ' ';
}

bool Bellman_Ford ( )
{
    vector < pi > :: iterator it;
    queue < int > q;

    int root, lng, node, cost;

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

    q.push(1);
    cnt[1] = 1;

    while ( !q.empty() )
    {
         root = q.front();
         q.pop();
         b[root] = 0;

         if ( cnt[root] == n )
         {
             fout << "Ciclu negativ!";
             return 0;
         }

         lng = v[root].size();

         for ( int i = 0; i < lng; i++ )
         {
             node = v[root][i].first;
             cost = v[root][i].second;

             if ( d[node] > d[root] + cost )
             {
                 d[node] = d[root] + cost;

                 if ( !b[node] )
                 {
                     q.push(node);
                     b[node] = 1;
                     cnt[node]++;
                 }
             }
         }
    }

    return 1;
}

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

    fin >> n >> m;

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

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