#include <fstream>
#include <vector>
#include <queue>
#define N 50010
using namespace std;
const int oo=1<<30;
int n,m,x,a,b,c,i,d[N],q[N],cnt[N];
vector <pair<int,int> > v[N];
queue<int> Q;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        d[i]=oo;
  d[1]=0;
  q[1]=1;
  Q.push(1);
  for(;Q.size();b++)
  {
      x=Q.front();
      Q.pop();
      q[x]=0;
      for(auto it:v[x])
        if(d[it.first]>d[x]+it.second)
            {
                d[it.first]=d[x]+it.second;
                if(!q[it.first])
                {
                    cnt[it.first]++;
                    if(cnt[it.first]==n)
                    {
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                    q[it.first]=1;
                    Q.push(it.first);
                }
            }

  }
  for(i=2;i<=n;i++)
    g<<d[i]<<" ";
    return 0;
}