#include <fstream>
#include <queue>
#include <vector>
#define f first
#define s second
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
vector<pair<int,int> > v[50001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;
int d[50001],n,m,a,b,c,nod,i;
int viz[50001];
int main()
{
 in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    v[a].push_back(make_pair(c,b));
}
for(i=1;i<=n;i++)
d[i]=100000001;
d[1]=0;
h.push(make_pair(0,1));
while(!h.empty())
{
    nod=h.top().s;
    h.pop();
        for(i=0;i<v[nod].size();i++)
    {
        if(d[v[nod][i].s]>d[nod]+v[nod][i].f)
          {
              viz[v[nod][i].s]++;
              d[v[nod][i].s]=d[nod]+v[nod][i].f;
              h.push(make_pair(d[v[nod][i].s],v[nod][i].s));
              if(viz[v[nod][i].s]==n)
              {
                  out<<"ciclu negativ";
                  return 0;
              }
          }
    }
}
   for(i=2;i<=n;i++)
   {
       out<<d[i]<<" ";
   }
    return 0;
}