#include <fstream>
#define INF 0x3f3f3f3f
#define dim 50001
#include <vector>
#include <queue>
#include <string.h>
#define x first
#define y second
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int viz[dim],i,m,n,a,b,c,frecv[dim],d[dim],nod;
vector < pair <int,int> > nodes[dim];
queue <int> q;
void Citire(int k)
{
    for(i=1;i<=k;i++)
    {
        fin>>a>>b>>c;
        nodes[a].push_back(make_pair(b,c));
    }
}
int main()
{
    fin>>n>>m;
    Citire(m);
    memset(d,INF,sizeof(d));
    d[1]=0;
    viz[1]=1;
    q.push(1);
    while(!q.empty())
    {
        nod=q.front();
        viz[nod]=0;
        for(i=0;i<nodes[nod].size();i++)
        {
            if(d[nod]+nodes[nod][i].y<d[nodes[nod][i].x])
            {
                d[nodes[nod][i].x]=d[nod]+nodes[nod][i].y;
                frecv[nod]++;
                if(frecv[nod]>=n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                if(viz[nodes[nod][i].x]==0)
                {
                    viz[nodes[nod][i].x]=1;
                    q.push(nodes[nod][i].x);
                }
            }
        }
        q.pop();
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}