#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

const int MAXN=50010;
const int INF=2e9;

vector <pair <int,int>> g[MAXN];
queue <int> q;
bool incoada[MAXN];
long long d[MAXN];
int n,m,numaru[MAXN];

int main()
{
    fin >>n>>m;
    for (int i=1;i<=m;++i){
        int x,y,cost;
        fin >>x>>y>>cost;
        g[x].push_back ({y,cost});
    }
    d[1]=0;
    for (int i=2;i<=n;++i)
        d[i]=INF;
    incoada[1]=true;
    q.push (1);
    while (q.empty ()==false){
        int nod=q.front ();
        q.pop ();
        incoada[nod]=0;
        for (int i=0;i<g[nod].size ();++i){
            int nodcrt=g[nod][i].first,costcrt=g[nod][i].second;
            if (costcrt+d[nod]<d[nodcrt]){
                d[nodcrt]=costcrt+d[nod];
                if (incoada[nodcrt]==false){
                    q.push(nodcrt);
                    incoada[nodcrt]=true;
                }
                numaru[nodcrt]++;
                if (numaru[nodcrt]>n){
                    fout <<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for (int i=2;i<=n;++i)
        fout <<d[i]<<' ';
    fin.close ();
    fout.close ();
    return 0;
}