#include <bits/stdc++.h>
#define NMAX 50009
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,d[NMAX],start;
int uz[NMAX];
vector <pair<int ,int> > v[NMAX];
priority_queue <int, vector<int> >C;
int INF;
void citire();
void dk(int start);
int main()
{INF=INT_MAX-1;
    citire();


    return 0;
}
void citire()
{
 int i,x,y,c;
 fin>>n>>m;
 start=1;
 for(i=1;i<=m;i++)
    {
     fin>>x>>y>>c;
     v[x].push_back(make_pair(y,c));
     //v[y].push_back(make_pair(x,c));
    }
  dk(start);
}
void dk(int start)
{
 int i,act;
 for(i=1;i<=n;i++)
        d[i]=INF;
 d[start]=0;
 C.push(start);
 while(!C.empty())
        {
         act=C.top();
         C.pop();
         uz[act]++;
         if(uz[act]>n)
            {fout<<"Ciclu negativ!";return;}

         for(i=0;i<v[act].size();i++)
            {
               if(d[act]+v[act][i].second < d[v[act][i].first])
                {d[v[act][i].first]=d[act]+v[act][i].second;
                 C.push(v[act][i].first);
                }
            }
        }
   for(i=2;i<=n;i++)
            fout<<d[i]<<" ";
}