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

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

int n, m, d[50001], cnt[50001];
bitset<50001> b;
vector<pair<int, int> > G[50001];
queue<int> Q;

void Read();
void B_Ford();

int main()
{
    Read();
    B_Ford();
    is.close();
    os.close();
    return 0;
}
void Read()
{
    is >> n >> m;
    for ( int i = 0, x, y, c; i < m; ++i )
    {
        is >> x >> y >> c;
        G[x].push_back({y, c});
    }
}
void B_Ford()
{
    int x;
    memset(d, 63, sizeof(d) );
    d[1] = 0;
    Q.push(1);
    while ( !Q.empty() )
    {
        x = Q.front();
        Q.pop();
        b[x] = false;
        vector<pair<int, int> > :: iterator it;
        for ( it = G[x].begin(); it != G[x].end(); it++)
            if ( d[it->first] > d[x] + it->second )
            {
                d[it->first] = d[x] + it->second;
                if ( b[it->first] ==  false )
                {
                    b[it->first] ==  true;
                    cnt[it->first]++;
                    if ( cnt[it->first] == n )
                    {
                        os << "Ciclu negativ!";
                        return;
                    }
                    Q.push(it->first);
                }
            }
    }
    for ( int i = 2; i <= n; ++i )
        os << d[i] << ' ';
}