#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector< pair < int, int> > v[500001];
int viz[500001],dist[500001],n,m,x,y,z;
bool inq[500001];
queue<int> q;
int bellmaford(int start)
{ int fiu, cost, nod;
  q.push(start);
  viz[start]++;
  while(!q.empty())
  { nod=q.front();
    q.pop();
    inq[nod]=0;
    for(int i=0;i<v[nod].size();i++)
    { fiu=v[nod][i].first;
      cost=v[nod][i].second;
      if(dist[nod]+cost<dist[fiu])
      { dist[fiu]=dist[nod]+cost;
          if(inq[fiu]==0)
          { q.push(fiu);viz[fiu]++;
             if(viz[fiu]>n) return 1;
             inq[fiu]=1;
          }
      }
    }
  }
  return 0;
}
int main()
{ f>>n>>m;
  for(int i=1;i<=m;i++)
  { f>>x>>y>>z;
    v[x].push_back({y,z});
  }
  for(int i=2;i<=n;i++)
    dist[i]=500000001;
  if(bellmaford(1)==1)
    g<<"Ciclu negativ!";
  else
    for(int i=2;i<=n;i++)
    g<<dist[i]<<" ";
    return 0;
}