#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct nodi
{
    int nod,cost;
};
vector <nodi> V[50001];
int n,m;
int nr[50001];
int d[50001];
queue <int> C;
int main()
{
    int i,v,x;
    nodi p;
fin>>n>>m;
for(i=1;i<=m;i++)
{
    fin>>x>>p.nod>>p.cost;
    V[x].push_back(p);
}
for(i=1;i<=n;i++)
    d[i]=999999;
d[1]=0;
C.push(1);
while(C.size()>0)
{
    v=C.front();
    C.pop();
    vector <nodi> :: iterator it;
    for(i=0;i<V[v].size();i++)
        if(V[v][i].cost+d[v]<d[V[v][i].nod])
        {
            C.push(V[v][i].nod);
            d[V[v][i].nod]=V[v][i].cost+d[v];
            nr[V[v][i].nod]++;
            if(nr[V[v][i].nod]>n)
            {
                fout<<"Ciclu negativ!";
                return 0;
            }
        }
}
for(i=2;i<=n;i++)
    fout<<d[i]<<" ";
    return 0;
}