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

#define INF 0x3f3f3f3f
#define MAX 50010

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

int n, m, cnt[MAX];
int x[MAX];
bool ok[MAX];
vector<pair<int, int > > G[MAX];
queue<int> Q;

void Read();
void BF();


int main()
{
    Read();
    BF();

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

void Read()
{
    is >> n >> m;
    int n1, n2, c;
    while( m-- )
    {
        is >> n1 >> n2 >> c;
        G[n1].push_back({n2, c});
    }
}

void BF()
{
    Q.push(1);
    memset(x, 63, sizeof(x) );
    x[1] = 0;
    int nod;
    while( !Q.empty() )
    {
        nod = Q.front();
        Q.pop();
        ok[nod] = false;
        for ( int i = 0; i < G[nod].size(); ++i )
        {
            if ( x[G[nod][i].first] > x[nod] + G[nod][i].second )
            {
                x[G[nod][i].first] = x[nod] + G[nod][i].second;
                if ( !ok[G[nod][i].first] )
                {
                    ok[G[nod][i].first] = true;
                    cnt[G[nod][i].first]++;
                    if ( cnt[G[nod][i].first] == n )
                    {
                        os << "Ciclu Negativ!";
                        return;
                    }
                    Q.push(G[nod][i].first);

                }

            }



        }
    }

    for ( int i = 2; i <= n; ++i )
        os << x[i] << ' ';

}