#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
#include <climits>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 50005, INF=INT_MAX;
vector<pair<int, int> > G[NMAX];
queue<int> q;
int viz[NMAX];
long long n, m, d[NMAX];

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y, c));
        ///G[y].push_back(make_pair(x, c));
    }
    for(int i=1; i<=n; ++i)
        d[i]=INF;
}

bool bellmanford(int s)
{
    q.push(s);
    d[s]=0;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        viz[nod]+=1;
        if(viz[nod]>n)
            return 0;
        for(auto vecin: G[nod])
            if(d[vecin.first]>d[nod]+vecin.second)
            {
                d[vecin.first]=d[nod]+vecin.second;
                q.push(vecin.first);
            }
    }
    return 1;
}


int main()
{
    citire();
    if(bellmanford(1))
        for(int i=2; i<=n; ++i)
            fout<<d[i]<<" ";
    else fout<<"Ciclu negativ!";
}