#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int n,m,Dmin[50001];
vector<vector<pair<int,int>>>G(50001);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>Q;
void init()
{
    for(int i=1;i<=n;++i)
        Dmin[i]=inf;

}
void dijkstra(int nod)
{
    init();
    Dmin[nod]=0;
    Q.push({nod,0});
    while(!Q.empty())
    {
        int nod=Q.top().first;
        int dist=Q.top().second;
        Q.pop();
        if(dist>Dmin[nod])
            continue;
        for(auto x:G[nod])
            if(Dmin[x.first]>Dmin[nod]+x.second)
            { 
                Dmin[x.first]=Dmin[nod]+x.second;
                Q.push({x.first,Dmin[x.first]});
            }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1,x,y,c;i<=m;++i)
    {
        cin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    dijkstra(1);
    int ok=0;
    for(int i=2;i<=n;++i)
        if(Dmin[i]!=inf)
            ok=1,cout<<Dmin[i]<<" ";
    if(ok==0)
        cout<<"Ciclu negativ";
    return 0;
}