#include <fstream>
#include <queue>
#define INF 1000000000

using namespace std;

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

int n,m,i,x,y,c,D[50001],IQ[50001],nod,cnt[50001];
queue<int> Q;
vector< pair<int, int> > L[50001];

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back(make_pair(y, c));
    }
    for (i=1; i<=n; i++)
        D[i] = INF;
    D[1] = 0;
    IQ[1] = 1;
    Q.push(1);
    while (!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        IQ[nod] = 0;
        for (i=0; i<L[nod].size(); i++)
        {
            int vecin = L[nod][i].first;
            int cost = L[nod][i].second;
            if (D[vecin] > D[nod]+cost)
            {
                D[vecin] = D[nod]+cost;
                if (IQ[vecin] == 0)
                {
                    Q.push(vecin);
                    IQ[vecin] = 1;
                    cnt[vecin]++;
                    if (cnt[vecin] == n)
                    {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for (i=2; i<=n; i++)
        fout << D[i] << " ";
    return 0;
}