#include <bits/stdc++.h>
#define NN 50005
using namespace std;
int n,m,x,y,z;
vector<vector<pair<int,int>>>G;
vector<int>d;
set<pair<int,int>>s;
bool ciclu_negativ;
int aparitii[NN];
void dijkstra()
{
    aparitii[1]=1;
    s.insert(make_pair(0,1));
    while(!s.empty() && ciclu_negativ==false)
    {
        int nod=s.begin()->second;
        s.erase(s.begin());
        for(const auto &f:G[nod])
        {
            if(d[f.second]>d[nod]+f.first)
            {
                aparitii[f.second]++;
                if(aparitii[f.second]>n)
                    ciclu_negativ=true;
                d[f.second]=d[nod]+f.first;
                s.insert(make_pair(d[f.second],f.second));
            }
        }
       // cout<<"\n";
    }
}
int main()
{
     freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    //freopen("dijkstra.in","r",stdin);
    //freopen("dijkstra.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    G=vector<vector<pair<int,int>>>(n+1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d\n",&x,&y,&z);
        G[x].push_back(make_pair(z,y));
    }
    d=vector<int>(n+1,INT_MAX);
    d[1]=0;
    dijkstra();
    if(ciclu_negativ)
        printf("Ciclu Negativ");
    else
    for(int i=2;i<=n;++i)
        printf("%d ",d[i]);
}