#include <fstream>
#include <deque>
#include <vector>
#define MX 50001
using namespace std;

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

struct muchie
{
    int j,c;
};

int n,m, intrat[MX], d[MX];
vector<muchie> v[MX];
bool viz[MX], cneg;
deque<int> q;

void Bellman()
{
    int u;
    vector<muchie>::iterator it;
    q.push_back(1);
    viz[1] = 1;

    while(!q.empty())
    {
        u = q.front();
        q.pop_front();
        viz[u] = 0;

        for(it=v[u].begin(); it!=v[u].end(); it++)
        {
            if(d[u] + it->c < d[it->j])
            {
                d[it->j] = d[u] + it->c;
                intrat[it->j]++;

                if(intrat[it->j] > n)
                {
                    cneg = 1;
                    return;
                }

                if(!viz[it->j])
                {
                    q.push_back(it->j);
                    viz[it->j] = 1;
                }
            }
        }
    }
}

int main()
{
    int i,x;
    muchie e;
    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>e.j>>e.c;
        v[x].push_back(e);
    }

    for(i=2; i<=n; i++) d[i] = (1<<30);

    Bellman();

    if(cneg)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(i=2; i<=n; i++) fout<<d[i]<<' ';
    }

    fin.close(); fout.close();
    return 0;
}