#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <queue>

using namespace std;

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

#define INF 1000000000

static const int NMAX  = 5e4+5;

int n, m;
vector<int> v[NMAX];
vector<pair<int,int> > M[NMAX];
bitset<NMAX> ok;
queue<int> Q;

int dmin[NMAX], in[NMAX];


void ReadInput()
{
    fin >> n >> m;
    int x,y,c;
    for(int i = 1; i<= m; ++i)
    {
        fin >> x >> y >> c;
        M[x].push_back(make_pair(y,c)); 
    }
    for(int i = 2; i<= n; ++i)
        dmin[i] = INF;

}
void BellmanFord()
{
    pair<int,int> aux;
    int i, vf;

    Q.push(1); ok[1] = 1; in[1] = 1;

    while(!Q.empty())
    {
        vf = Q.front(); Q.pop(); ok[vf] = 0;
        for(i = 0; i < M[vf].size(); ++i)
        {
            aux = M[vf][i];
            if(dmin[aux.first] > dmin[vf] + aux.second)
            {
                dmin[aux.first] = dmin[vf] + aux.second;
                if(ok[aux.first] == 0)
                {
                    ok[aux.first] = 1;
                    ++in[aux.first];
                    Q.push(aux.first);
                    if(in[aux.first] > n)
                    {
                        fout << "Ciclu Negativ";
                        return;
                    }
                }
            }
        }
    }
    for(i = 2; i<=n; ++i)
        fout << dmin[i] << " ";
}

int main()
{
    ReadInput();
    BellmanFord();
    return 0;
}