#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stdlib.h>
using namespace std;

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


struct muchie
{
    int nod;
    int cost;
};
  int viz[250009];
vector <muchie> v[250009];
int N, M;
queue <int>q;
int costuri[250009];

/// costuri[i] = costul minim cu care pot ajunge la nodul i, plecand din nodul 1 (sau nodu sursa la modu general)




void Citire()
{
    int x, y, cost;
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> x >> y >> cost;
        muchie w;
        w.nod = y;
        w.cost = cost;
        v[x].push_back(w);
    }
}

void Bellman_Ford()
{

    int k;
    q.push(1);

    while(!q.empty())
    {
        k=q.front();
        for(int i=0; i<v[k].size(); i++)
        {
            int D=v[k][i].nod;
            int d=v[k][i].cost;

            if(viz[D]==0 || (costuri[k]+d<costuri[D]))
            {  /// cout<<'x';
                costuri[D]=costuri[k]+d;
                viz[D]++;
                q.push(D);
                if(viz[D]==N+1)
                {
                    fout<<"Ciclu negativ!";
                    exit(0);
                }
            }
        }
        q.pop();

    }

}

void Afisare()
{
    int i;
    for(i=2; i<=N; i++)
        fout<<costuri[i]<<' ';
}

int main()
{


    Citire();
    Bellman_Ford();
    Afisare();
    return 0;
}