#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define nmax 50099
#define INF 0x7FFFFFFF;
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector < pair<int ,int > > G[nmax];
int n,start,negativ;
int dmin[nmax],nr[nmax];
queue <int > C;

void citire();
void Bellman_Ford();
void afisare();

int main()
{
    citire();
    Bellman_Ford();
    afisare();
}

void citire(){
int m,x,y,c;
fin>>n>>m;
start=1;
while(m--)
{fin>>x>>y>>c;
    G[x].push_back(make_pair(y,c));
}
}

void afisare(){
if(negativ==1)fout<<"Ciclu negativ!";
else
for(int i=2;i<=n;i++)fout<<dmin[i]<<' ';
}

void Bellman_Ford(){int i;
for(i=1;i<=n;i++)dmin[i]=INF;dmin[start]=0;
C.push(start);
int x;
while(!C.empty() && !negativ){
    x = C.front();
        C.pop();

for(int i=0;i<G[x].size();i++)
    if(dmin[G[x][i].first]> dmin[x]+G[x][i].second)
    {
        dmin[G[x][i].first]=dmin[x]+G[x][i].second;
        nr[G[x][i].first]++;
        C.push(G[x][i].first);
        if(nr[G[x][i].first]>n)negativ=1;
    }


}
}