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

int maxn=(1<<30);
queue <int> q;
vector <int> v[50010],c[50010];
int sol[50010],trec[50010], i, n, m, ciclu,aux,next;


int main()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
    int x,y ,z;
    f>>x>>y>>z;
    v[x].push_back(y);
    c[x].push_back(z);

}
for (i=2;i<=n;i++)
{
    sol[i]=maxn;
}
q.push(1);
while (!q.empty())
{
    aux=q.front();
    q.pop();
    trec[aux]++;
    if (trec[aux]>n) {ciclu=1;break;}
    for (i=0;i<v[aux].size();i++)
    {
        next=v[aux][i];
        if (sol[next]>sol[aux]+c[aux][i]) {
            sol[next]=sol[aux]+c[aux][i];
            trec[next]++;
            q.push(next);
        }
       // if (trec[next]>n) {ciclu=1;break;}
    }

}
    if (ciclu==1) g<<"Ciclu negativ!";
    else for (i=2;i<=n;i++) g<<sol[i]<<" ";


    return 0;
}