#include <fstream>
#include <vector>
#include <queue>


using namespace std;

const static int NMAX = 50001;
const static int INFINIT = 1001 * NMAX;

vector < pair<int,int> > graf[NMAX];
int costuri[NMAX];
int nr_ap_coada[NMAX];
bool in_queue[NMAX];


int nr_noduri;
int nr_muchii;
queue <int> coada;

int main()
{
    ifstream input("bellmanford.in");
    ofstream output("bellmanford.out");
    input >> nr_noduri;
    input >> nr_muchii;

    for (int i =0;i<nr_muchii;i++)
    {
        int src , dest , cost;
        input >> src >> dest >> cost;
        graf[src].push_back(make_pair(dest,cost));
    }

    bool ciclu = false;
    fill(costuri+1,costuri+nr_noduri+1,INFINIT);
    fill(nr_ap_coada+1,nr_ap_coada + nr_noduri+1,0);

    costuri[1] = 0;
    nr_ap_coada[1] = 1;
    coada.push(1);
    in_queue[1] = true;

    int nod = 1;
    while (!ciclu && !coada.empty())
    {
        nod = coada.front();
        coada.pop();
        in_queue[nod] = false;
        for (int i =0;i<graf[nod].size();i++)
        {
            pair <int,int> x = graf[nod][i];
            if (costuri[nod] + x.second < costuri[x.first])
            {
                costuri[x.first] = costuri[nod] + x.second;
                if (!in_queue[x.first])
                {
                    if (nr_ap_coada[x.first] > nr_noduri)
                    {
                        ciclu = true;
                    }
                    else
                    {
                        coada.push(x.first);
                        in_queue[x.first] = true;
                        nr_ap_coada[x.first] ++;
                    }
                }
            }
        }
    }

    if (ciclu)
    {
        output << "Ciclu negativ!";
    }
    else
    {
        for (int i =2;i<=nr_noduri;i++)
        {
            output << costuri[i] << " ";
        }
    }




    return 0;
}