#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int NMAX=50000;
const int Inf=0x3f3f3f3f;

int N,M,d[NMAX],cnt[NMAX];
vector< pair<int,int> > G[NMAX];
bool inQ[NMAX];
queue<int> Q;

int main()
{
    int i,j,k;
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    
    fin>>N>>M;
    while (M--)
    {
          fin>>i>>j>>k;
          --i;--j;
          G[i].pb(mp(j,k));
    }
    
    for (i=0;i<N;++i) inQ[i]=false, d[i]=Inf, cnt[i]=0;
    d[0]=0, inQ[0]=true, cnt[0]=1;
    for (Q.push(0);!Q.empty();Q.pop())
    {
        k=Q.front();
        vector< pair<int,int> >::iterator it;
        for (it=G[k].begin();it!=G[k].end();++it)
           if (d[it->ff] > d[k] + it->ss)
           {
               d[it->ff] = d[k] + it->ss;
               if (!inQ[it->ff])
               {
                   Q.push(it->ff);
                   inQ[it->ff]=true;
                   cnt[it->ff]++;
                   if (cnt[it->ff]==N)
                   {
                        fout<<"Ciclu negativ!";
                        return 0;
                   }
               }
           }
        inQ[k]=false;
    }
    
    for (i=1;i<N;++i) fout<<d[i]<<' ';
    
    return 0;
}