#include <fstream>
#include <queue>
#include <cstring>
#define NMAX 50010
#define Inf 0x3f3f3f3f

using namespace std;

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

struct graf{
    int neighbour;
    int cost;
    graf *next;
}*a[250010];

queue <int> c;
int n, m, freq[NMAX], d[NMAX];
bool used[NMAX];

void add(int x, int y, int price);

int main()
{
    int x, y, price, i, v;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> price;
        add(x, y, price);
    }
    memset(d, Inf, sizeof(d));
    d[1] = 0;
    c.push(1);
    used[1] = 1;
    while(!c.empty())
    {
        v = c.front();
        c.pop();
        used[1] = 0;
        for(graf *nod = a[v]; nod != NULL; nod = nod -> next)
            if(d[nod->neighbour] > d[v] + nod->cost)
            {
                d[nod->neighbour] = d[v] + nod->cost;
                c.push(nod->neighbour);
                if(!used[nod->neighbour])
                {
                    used[nod->neighbour]= 1;
                    if(++freq[nod->neighbour] > n)
                    {
                        fout << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
    }
    for(i = 2; i <= n; i++)
        fout << d[i]<< ' ';
    fout << '\n';
    return 0;
}

void add(int x, int y, int price)
{
    graf *nod = new graf;
    nod -> neighbour = y;
    nod -> cost = price;
    nod -> next = a[x];
    a[x] = nod;
}