#include <bits/stdc++.h>
using namespace std;

#define lsize(x) la[x].v.size()
#define to(x,i) la[x].v[i].first
#define cost(x,i) la[x].v[i].second

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

const int N=50005,INF=10000000;
int dist[N],frecv[N];

struct graf
{
    vector <pair<int,int> >v;
}la[N];

bool bellford(int src,int n)
{
    for(int i=1;i<=n;i++) dist[i]=INF;
    dist[src]=0;

    queue<int> q;
    q.push(src);

    while(!q.empty())
    {
        int nod=q.front();
        if(++frecv[nod]>n) return 0;

        for(int i=0;i<lsize(nod);i++)
            if(dist[nod]+cost(nod,i) < dist[to(nod,i)])
        {
            dist[to(nod,i)]=dist[nod]+cost(nod,i);
            q.push(to(nod,i));
        }

        q.pop();
    }

    return 1;
}

int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int from,to,cost;
        in>>from>>to>>cost;
        la[from].v.push_back(make_pair(to,cost));
    }

    if(bellford(1,n))
    {
        for(int i=2;i<=n;i++)
            out<<dist[i]<<' ';
    }
    else out<<"Ciclu negativ!";
    return 0;
}