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

#define DIM 50010
#define INF 2000000000

using namespace std;

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

vector <pair <int, int > > L[DIM * 5];

int D[DIM], Ciclu[DIM];
int n, m, x, y, cost, a;

queue <int> Q;

bitset<DIM> v;

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y,cost));
    }

    for(int i = 2; i <= DIM; i ++)
    {
        D[i] = INF;
    }

    Q.push(1);

    bitset<1> ok = 1;
    v[1] = 1;

    while(!Q.empty())
    {
        a = Q.front();
        Q.pop();
        v[a] = 0;

        for(int i = 0; i < L[a].size(); i ++)
        {
            if(D[ L[a][i].first ] > D[a] + L[a][i].second )
            {
                D[ L[a][i].first ] = D[a]  + L[a][i].second;
                if(v[ L[a][i].first ] == 0)
                {
                    Q.push(L[a][i].first);
                    v[ L[a][i].first ] = 1;
                    Ciclu[a]++;

                    if(Ciclu[a] == n)
                    {
                        fout << "Ciclu negativ!";
                        ok = 0;
                    }
                }
            }
            if(ok == 0)
            {
                break;
            }
        }
        if(ok == 0)
        {
            break;
        }
    }

    if(ok == 1)
    {
        for(int i = 2; i <= n; i ++)
            fout << D[i] << " ";
    }



    return 0;
}