#include <fstream>
#include<vector>
#include<cstring>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,dist[50003],pre[50003],j;
const int INF=0x3f3f3f3f;
struct edge{int x; int y; int c;}edg;
vector<edge>e;
vector<edge>::iterator it1;
vector<pair<int, int> >v[50003];
vector<pair<int, int> > ::iterator it;

int main()
{
    int i,x,y,c,to,cost,k,from;
    f>>n>>m;
    edge aux;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        aux.x=x; aux.y=y; aux.c=c;
        e.push_back(aux);
    }
    memset(dist, INF, sizeof dist);
    dist[1]=0;
    for(k=1;k<n;k++){
        for(it1=e.begin();it1!=e.end();++it1)
        {
            from=it1->x; to=it1->y; cost=it1->c;
            if(dist[from]+cost<dist[to])
            {
                dist[to]=dist[from]+cost;
                pre[to]=i;
            }
        }
    }
    for(it1=e.begin();it1!=e.end();++it1)
        {
            from=it1->x; to=it1->y; cost=it1->c;
            if(dist[from]+cost<dist[to]) {
                g<<"Ciclu negativ!"<<'\n';
                f.close();
                g.close();
                return 0;
            }
        }
    for(i=2;i<=n;i++) g<<dist[i]<<' ';
    f.close();
    g.close();
    return 0;
}