#include<cstdio>
#include<vector>
#include<queue>
#define _NMAX 50010
#define _MMAX 250010
#define INF 1<<30
using namespace std;

int nN, nM;
struct muchie
{
    int dest, cost;
};
vector<muchie > lAd[_NMAX];
int dist[_NMAX];

bool bford();
int main()
{
    FILE *f=fopen("bellmanford.in", "r");
    fscanf (f, "%d %d", &nN, &nM);
    for (int i=1;i<=nM;i++)
    {
        int nod; muchie tmp;
        fscanf (f,"%d %d %d", &nod, &tmp.dest, &tmp.cost);
        lAd[nod].push_back(tmp);
    }
    f=fopen("bellmanford.out", "w");
    if (bford()==0)//dist[]
        for (int i=2;i<=nN;i++)
            fprintf(f, "%d ", dist[i]);
    else
        fprintf(f, "Ciclu negativ!");
}

int nEval[_NMAX];
bool bford()
{
    for (int i=2;i<=nN;i++) dist[i]=INF;
    queue<int > q;
    q.push(1); nEval[1]=1;
    while (!q.empty())
    {
        int cur=q.front(); q.pop();
        for (int i=0;i<lAd[cur].size();i++)
        {
            muchie mcur=lAd[cur].at(i);
            if (dist[cur]+mcur.cost < dist[mcur.dest])
            {
                if (nEval[mcur.dest]==nN) return 1;
                dist[mcur.dest] = dist[cur]+mcur.cost;
                q.push(mcur.dest); nEval[mcur.dest]++;
            }
        }
    }
    return 0;
}