#include <fstream>
#define INF 1 << 13

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct Nod
{
    int nod,cost;
    Nod *urm;
};
typedef Nod *PNod;

PNod L[50001];
int d[50001],t[50001],n,m;

void add(int x, int y, int c)
{
    PNod p = new Nod;
    p -> nod = y;
    p -> cost = c;
    p -> urm = L[x];
    L[x] = p;
}

int relax()
{
    PNod p;
    int rasp = 0;
    for(int j = 1; j <= n; j++)
        for(p = L[j]; p; p = p -> urm)
            if(d[p -> nod] > d[j] + p -> cost)
            {
                d[p -> nod] = d[j] + p -> cost;
                t[p -> nod] = j;
                rasp = 1;
            }
    return rasp;
}

int main()
{
    int x,y,c,r;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        add(x,y,c);
    }

    for(int i = 1; i <= n; i++) d[i] = INF;
    d[1] = 0;

    for(int l = 1; l <= n - 1; l++)
    {
        r = relax();
        if(r == 0) l = n + 1;
    }

    r = relax();
    if( r == 1 )
        g << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            g << d[i] << " ";
    return 0;
}