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

using namespace std;

FILE *fin = fopen ("bellmanford.in", "r");
ofstream fout ("bellmanford.out");

vector <int> G[100010], cost[100010];
queue <int> C;
int n, m;
int dist[100010], martor[100010], contor[100010];

int main()
{
    int i, j;
    int x, y, c;
    fscanf (fin, "%d %d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        fscanf (fin, "%d %d %d", &x, &y, &c);
        G[x].push_back (y);
        cost[x].push_back (c);
    }

    for (i = 2; i <= n; i++) dist[i] = 1e9;
    C.push(1); martor[1] = 1; // am introdus nodul de la care plec si am marcat ca l-am introdus
    contor[1] = 1;
    while (C.size()) // mai am elem in coada
    {
        int prim = C.front(); // ia primul element din coada
        C.pop(); // scoate primul element din coada
        martor[prim] = 0;
        for (i = 0; i < G[prim].size(); i++)
            if (dist[G[prim][i]] > dist[prim] + cost[prim][i])
            {
                dist[G[prim][i]] = dist[prim] + cost[prim][i];
                if (martor[G[prim][i]] == 0) // nodul G[prim][i] nu este in in coada, asa ca il vom adauga pt o verificare ulterioara
                {
                    martor[G[prim][i]] = 1;
                    C.push(G[prim][i]);
                    contor[G[prim][i]]++;
                    if (contor[G[prim][i]] > n)
                    {
                        fout << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
    }

    for (i = 2; i <= n; i++) fout << dist[i] << ' ';
    fout << '\n';
    return 0;
}