#include <bits/stdc++.h>
#define oo INT_MAX-1
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

typedef pair <int,int> pereche;

vector<pereche> V[50005];
int n,m,cost[50005],viz[50005],x,y,c;
queue <int> C;

void solve(){
int i,vf;
for(i=2;i<=n;++i) cost[i]=oo;
C.push(1);
while(!C.empty())
{ vf=C.front();
  C.pop();
  viz[vf]++;
  if(viz[vf]>n){fout<<"Ciclu negativ!";return;}
  for(auto x:V[vf])
  { if(cost[vf]+x.second< cost[x.first])
         { cost[x.first]=cost[vf]+x.second;
           C.push(x.first);
         }
   }
}

for(i=2;i<=n;++i) fout<<cost[i]<<' ';
}

int main()
{  fin>>n>>m;
   for(int i=1;i<=m;++i){
    fin>>x>>y>>c;
    V[x].push_back(make_pair(y,c));
   }
   solve();
   fin.close(); fout.close();

    return 0;
}