#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct vecini{
    int e1, cost;
};

int n, m, viz[50005], h[50005];
vector <vecini> L[50005];
queue <int> q;

void citire()
{
    fin >> n >> m;
    int x, y, c;
    while(m--)
    {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
    for(int i=1;i<=n;i++)
        h[i]=99999999;
}

int bellmanford(int nod)
{
    viz[nod]++;
    q.push(nod);
    h[nod]=0;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(unsigned int i=0;i<L[v].size();i++)
        {
            int vecin = L[v][i].e1;
            if(h[v]+L[v][i].cost<h[vecin] && viz[vecin]!=n-1)
            {
                h[vecin]=h[v]+L[v][i].cost;
                viz[vecin]++;
                q.push(vecin);
            }
            if(viz[vecin]==n-1)
                return 0;
        }
    }
    return 1;
}

int main()
{
    citire();
    int ok=bellmanford(1);
    if(ok==0)
        fout << "Ciclu negativ!" << endl;
    else
    {
        for(int i=2;i<=n;i++)
        {
            fout << h[i] << " ";
        }
    }
    return 0;
}