#include <fstream>
#include <vector>
#include <queue>
#define fr first
#define sc second

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int NMAX=5e4+5, INF=1e9;
int n, m, dist[NMAX], cnt[NMAX];
vector<pair<int, int>> adj[NMAX];
queue<int> q;

bool BF(int st)
{
    q.push(st); dist[st]=0;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(auto ev:adj[u])
            if(dist[ev.fr]>dist[u]+ev.sc)
            {
                cnt[ev.fr]++;
                if(cnt[ev.fr]>=n)
                    return 0;
                
                dist[ev.fr]=dist[u]+ev.sc;
                q.push(ev.fr);
            }
    }
    return 1;
}

int main()
{
    in>>n>>m;
    while(m--)
    {
        int a, b, c; in>>a>>b>>c;
        adj[a].push_back({b, c});
    }
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    
    if(BF(1))
        for(int i=2;i<=n;i++)
            out<<dist[i]<<" ";
    else
        out<<"Ciclu negativ!";
        
    return 0;
}