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

using namespace std;
const int NMAX = 50001, //MMAX = 250001,
          INF = 0x77FFFFFF;

struct muchie
{
    int y, w;

//    bool operator<(const muchie &m) const
//    {
//        return w > m.w;
//    }
};

int N, M,
    D[NMAX]; ///D[i] = distanta minima de la nodul src la i
int nrViz[NMAX];
vector<muchie> G[NMAX];
queue<int> Q;
bool inQ[NMAX];

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

void citire()
{
    int x, y, w;
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        f >> x >> y >> w;
        G[x].push_back({y, w});
    }
}

void init(int src)
{
    for(int i = 1; i <= N; i++)
        D[i] = INF;
    D[src] = 0;
}

bool BellmanFord(int src)
{
    int crt, dest, cost;
    init(src);
    Q.push(src);
    inQ[src] = 1;
    while(!Q.empty())
    {
        crt = Q.front();
        Q.pop();
        inQ[crt] = 0;
        for(muchie &m : G[crt])
        {
            cost = D[crt] + m.w;
            dest = m.y;
            if(cost < D[dest])
            {
                D[dest] = cost;
                if(inQ[dest] == 0)
                {
                    Q.push(dest);
                    nrViz[dest]++;
                    if(nrViz[dest] > N)
                        return 0; ///ciclu negativ!
                }
            }
        }
    }
    return 1;
}

int main()
{
    citire();
    if(BellmanFord(1))
    {
        for(int i = 2; i <= N; i++)
            g << D[i] << ' ';
    }
    else
        g << "Ciclu negativ!";
    f.close();
    g.close();
    return 0;
}