#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int inf = 1073741824;
int n, m;
vector<pair<int, int> > vecini[50005];
int viz[50005];
int sol[50005];
void citire(){
scanf("%d %d", &n, &m);
int tmp1, tmp2, tmp3;
for(int i = 0; i < m; i++){
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
tmp1--;
tmp2--;
vecini[tmp1].push_back({tmp2, tmp3});
}
for(int i = 0; i < n; i++){
sol[i] = inf;
}
}
int solve(){
queue<pair<int, int> > Q;
Q.push({0, 0});
while(!Q.empty()){
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
viz[x]++;
sol[x] = y;
if(viz[x] > n){
printf("Ciclu negativ!");
return 0;
}
int l = vecini[x].size();
for(int i = 0; i < l; i++){
int d = sol[x] + vecini[x][i].second;
if(d < sol[vecini[x][i].first]){
Q.push({vecini[x][i].first, vecini[x][i].second + sol[x]});
}
}
}
return 1;
}
int main()
{
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
citire();
if(solve() != 0){
for(int i = 1; i < n; i++){
printf("%d ", sol[i]);
}
}
return 0;
}