#include <fstream>
#include <deque>
#include <vector>
#define INF 2000000000
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int x,y,z,i,n,m,j,f[50005],d[50005],nr[50005],nod,vecin;
vector< pair<int,int> > v[50005];
deque<int> c;
int main()
{
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>x>>y>>z;
v[x].push_back(make_pair(y,z));
}
for(i=1;i<=n;i++)
{
    f[i]=0;
    d[i]=INF;
}
d[1]=0;
f[1]=1;
nr[1]=1;
c.push_back(1);
while(!c.empty())
{
nod=c[0];
for(i=0;i<v[nod].size();i++)
{
vecin=v[nod][i].first;
if(d[vecin]>d[nod]+v[nod][i].second)
{
d[vecin]=d[nod]+v[nod][i].second;
if(f[vecin]==0)
{
    nr[vecin]++;
    if(nr[vecin]==n)
    {
out<<"Ciclu negativ!";
return 0;
    }
    c.push_back(vecin);
    f[vecin]=1;
}
}
}
c.pop_front();
f[nod]=0;
}
for(i=2;i<=n;i++)
{
out<<d[i]<<" ";
}
return 0;
}