#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream ka("dijkstra.in");
ofstream ki("dijkstra.out");

const int N_MAX = 50000;
const int M_MAX = 250000;

int n, m, x, y, c, distanta[N_MAX + 1], aparitii[N_MAX + 1];

struct muchie
{
    int vecin;
    int cost;

    muchie(int vecin, int cost) {
        this->vecin = vecin;
        this->cost = cost;
    }
};

vector<muchie> vecini[N_MAX + 1];
bool inCoada[N_MAX + 1];
queue <int> coada;

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        //muchie muchie;
        int x, y, c;
        ka >> x >> y >> c;
        vecini[x].push_back(muchie(y, c));
    }
    for(int i = 2; i <= n; i++)
    {
        distanta[i] = 0x3fffffff;
        inCoada[i] = false;
    }
    distanta[1] = 0;
    inCoada[1] = true;
    coada.push(1);
    bool cicluNegativ = false;
    while(!coada.empty() && !cicluNegativ)
    {
        int nod = coada.front();
        coada.pop();
        inCoada[nod] = false;
	 aparitii[nod]++;
	 if(aparitii[nod] == n)
	 	cicluNegativ = true;
        for(int i = 0; i < vecini[nod].size(); i++)
            if(distanta[nod] + vecini[nod][i].cost < distanta[vecini[nod][i].vecin])
            {
                distanta[vecini[nod][i].vecin] = distanta[nod] + vecini[nod][i].cost;
                if(!inCoada[vecini[nod][i].vecin])
                {
coada.push(vecini[nod][i].vecin);
                	inCoada[vecini[nod][i].vecin] = true;
                }
            }
    }

    if(cicluNegativ)
        ki << "Ciclu negativ!\n";
    else
        for(int i = 2; i <= n; i++)
            ki << distanta[i] << " ";
    return 0;
}