#include <fstream>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <bitset>

#define pb push_back
#define mp make_pair
#define MAXXX 50005
#define inf ((1<<31)-1)
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

void read();
void solve();

int n, m;
vector< pair<int, int> > G[ MAXXX ]; vector<int> d( MAXXX , inf ), nr(MAXXX);
queue < int > Q;
bitset < MAXXX > viz;

int main()
{
    read();
    solve();
    cin.close();
    cout.close();
    return 0;
}

void read()
{
    cin>>n>>m;
    for(int i = 1 , a, b, c ; i <= m ;++ i)
    {
        cin >> a >> b >> c ;
        G[a].pb ( mp(b, c) );
    }
}

void solve()
{
    Q.push(1);
    d[1] = 0;
    viz[1] = true;
    for( ; !Q.empty(); Q.pop() )
    {
        int nod = Q.front();
        viz [ nod ] = false;
        for(vector< pair<int, int> >::iterator it = G[nod].begin(); it!=G[nod].end(); ++it)
        {
            int node = it->first;
            int cost = it->second;
            if( d[node] > d[nod] + cost )
            {
                d[node] = d[nod] +cost;
                if( !viz[node] )
                {
                    if( nr[node] > n )
                    {
                        cout<<"Ciclul negativ!\n";
                        return ;
                    }
                    viz[node] = 1;
                    Q.push(node);
                    ++nr[node];
                }
            }
        }
    }
    for(int i = 2;  i <= n ; ++ i)
        cout<<d[i]<<" ";
    cout<<"\n";
}