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

using namespace std;
#define NMAX 50005
#define inf 1e9
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector<pair<int, int> > graf[NMAX];
queue<int> coada;



int n,m, distanta[NMAX], viz[NMAX];
void citire()
{
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        f>>a>>b>>c;
        graf[a].push_back({b,c});
    }
}



bool bellmanford()
{
    for(int i = 2; i <= n; i ++)
        distanta[i] = inf;
    coada.push(1);
    while(!coada.empty())
    {

        int x = coada.front();
        coada.pop();
        if(viz[x] > n)
        {
            g<<"Ciclu negativ\n";
            return false;
        }
        viz[x] ++;
        for(int i = 0; i < graf[x].size();  i ++)
        {
            int vecin = graf[x][i].first;
            int cost = graf[x][i].second;
            if(distanta[x] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[x] + cost;
                coada.push(vecin);
            }
        }
    }
    return true;

}

void afisare()
{
    for(int i = 2; i <= n; i ++)
        g<<distanta[i]<<" ";

}
int main()
{
    citire();
    if(bellmanford() == true)
        afisare();
    return 0;
}