#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
#define n_N  50001
queue<int>_q;
bool viz[n_N];
int d[n_N];
struct my_struct {

    int nod, cost;
}t;
vector<my_struct> v[250022];

int a,b,Cost,cont_lant[n_N],n, m;
void marcare(int n)
{
    int k=10000101;
    for(int i=1;i<=n;i++)
    {
        d[i]=k;
    }
}
int  bell_ford(int a)
{

    viz[1] = 1;
    marcare(n);
    _q.push(a);
    int new_nod;
    d[1] = 0;
    bool lantNO=0;
    while (!_q.empty()&&!lantNO)
    {
        new_nod = _q.front();
        _q.pop();
        viz[new_nod] = 0;
        //parcurg vecini
        ///for (vector<my_struct>::iterator it = v[nod].begin(); it < v[nod].end(); it++)
        for(int i=0;i<v[new_nod].size();i++)
        {
            t=v[new_nod][i];
            if(d[new_nod]+t.cost<d[t.nod])
            {
                d[t.nod]=d[new_nod]+t.cost;
                if(!viz[t.nod])
                {
                    if(cont_lant[t.nod]>n)
                        lantNO=1;
                    else{
                        cont_lant[t.nod]++;
                        viz[t.nod]=1;
                        _q.push(t.nod);
                    }
                }
            }

        }
    }
    return lantNO;
}
int main() {
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> a >> b >> Cost;
        t.nod = b;
        t.cost = Cost;
        v[a].push_back(t);
    }
    if(bell_ford(1))
    {
        g<<"Ciclu negativ";
    }
    else{
        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
}