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

using namespace std;

const int HIGH = 10000000;
const int N_LIM = 50001;

struct nxt
{
    int n, c;

    nxt(int _n = 0, int _c = 0)
    : n(_n), c(_c) {}

    friend bool operator>(const nxt& p, const nxt& q)
    {
        return p.c > q.c;
    }
};

int N, M, dist[N_LIM], cnt[N_LIM];
bool viz[N_LIM], inQ[N_LIM];
vector<nxt> L[N_LIM];

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

void bellmanford(int s)
{
    queue<int> pq;
    inQ[s] = true;
    cnt[s] = 1;
    pq.push(s);

    while(!pq.empty())
    {
        int n = pq.front();
        pq.pop();
        inQ[n] = false;

        for(const auto& [p, q] : L[n])
        {
            if(dist[n] + q < dist[p])
            {
                dist[p] = dist[n] + q;
        
                if(!inQ[p])
                {
                    inQ[p] = true;
                    pq.push(p);
                    cnt[p]++;

                    if(cnt[p] > N)
                    {
                        fout << "Ciclu negativ!";
                        exit(0);
                    }
                }
            }
        }
    }
}

void init(int s)
{
    for(int i = 1; i <= N; i++)
        viz[i] = false, dist[i] = (i == s ? 0 : HIGH), cnt[i] = 0;
}

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        L[a].push_back(nxt(b, c));
    }

    init(1);
    bellmanford(1);

    for(int i = 2; i <= N; i++)
        fout << (dist[i] >= HIGH ? 0 : dist[i]) << ' ';

    return 0;
}