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

using namespace std;

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

const int NMAX = 50000 + 1;
const int INF = 0x3fffffff;
int N, M;
int cost[NMAX], vizitat[NMAX];
bool inQ[NMAX];
queue <int> Q;
vector < pair <int, int> > graf[NMAX];

void read()
{
    int a, b, c;
    in >> N >> M;
    for (int i = 1; i <= M; i++) {
        in >> a >> b >> c;
        graf[a].push_back(make_pair(b, c));
    }
}

void write()
{
    for (int i = 2; i <= N; i++)
        out << cost[i] << ' ';
}

bool BellmanFord()
{
    for (int i = 2; i <= N; i++) cost[i] = INF;
    inQ[1] = true;
    Q.push(1);
    vizitat[1] = 1;

    int nod, l, fiu, c;

    while(!Q.empty())
    {
        nod = Q.front(); Q.pop(); inQ[nod] = false;
        if (vizitat[nod] > N) return true;
        l = graf[nod].size();
        for (int i = 0; i < l; i++)
         {
            fiu = graf[nod][i].first;
            c = graf[nod][i].second + cost[nod];
            if (c < cost[fiu])
            {
                cost[fiu] = c;
                Q.push(fiu); inQ[fiu] = true;
                vizitat[fiu]++;
            }
        }
    }
    return false;
}

int main()
{
    read();
    bool ok = BellmanFord();
    if (!ok) write();
    else out << "Ciclu negativ!";
    out << '\n';
    return 0;
}