#include <bits/stdc++.h>
#define oo 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int MAX_N = 50005;
int n,m;
struct nod
{
    int y;
    int cost;
};
int dmin[MAX_N],viz[MAX_N],nr[MAX_N];
queue<int> q;
vector<nod>Q[MAX_N];

void Citire()
{
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        Q[x].push_back({y,c});
    }
    f.close();
}

void Solve()
{
    for(int i=2;i<=n;++i)
        dmin[i] = oo;
    q.push(1);
    viz[1] = 1;
    while(!q.empty())
    {
        int x = q.front();
        for(auto &v:Q[x])
        {
            if(dmin[v.y] > dmin[x] + v.cost)
            {
                dmin[v.y] = dmin[x] + v.cost;
                if(viz[v.y] == 0) q.push(v.y);
                nr[v.y]++;
                viz[v.y] = 1;
                if(nr[v.y] >= n)
                {
                    g<<"Ciclu negativ!";
                    exit(0);
                }
            }
        }
        viz[x] = 0;
        q.pop();
    }
}

void Afisare()
{
    for(int i=2;i<=n;++i)
        g<<dmin[i]<<" ";
    g.close();
}
int main()
{
    Citire();
    Solve();
    Afisare();
    return 0;
}