#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

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

struct edge
{
    int to, cost;
};

const int NMAX = 50000, INF = 0x3f3f3f3f;

queue<edge> coada;
vector<edge> graf[NMAX + 5];
int n, m, cost[NMAX + 5], numar_vizite[NMAX + 5];

// Algoritmul Bellman-Ford
// Problema se rezolva in maximum n-1 iterari, altfel exista un ciclu negativ
// Imbunatatim costurile nodurilor vecine, plecand din nodul de start specificat

void bellmanFord(int start)
{
    memset(cost, INF, sizeof cost);
    cost[start] = 0;
    coada.push({1,0});
    bool ciclu_negativ = false;
    while (!coada.empty() && !ciclu_negativ)
    {
        edge curent = coada.front();
        coada.pop();
        int nod_curent = curent.to;
        for (int i = 0; i < graf[nod_curent].size(); i++)
        {
            edge it = graf[nod_curent][i];
            numar_vizite[it.to]++;
            // Am depasit numarul maxim de iterari posibile in nod
            if (numar_vizite[it.to] == n)
            {
                ciclu_negativ = true;
                break;
            }
            // Un cost mai bun, atunci recalculam si vecinii acestui nod
            if (cost[it.to] > cost[nod_curent] + it.cost)
            {
                cost[it.to] = cost[nod_curent] + it.cost;
                coada.push({it.to, cost[it.to]});
            }
        }
    }
    if (ciclu_negativ)
    {
        fout << "Ciclu negativ!\n";
        exit(0);
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int from;
        edge it;
        fin >> from >> it.to >> it.cost;
        graf[from].push_back(it);
    }
    bellmanFord(1);
    for (int i = 2; i <= n; i++)
        fout << cost[i] << " ";
    fout << "\n";
    return 0;
}