#include <bits/stdc++.h>
#define N 50000

using namespace std;

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

queue <int> Q;
vector < pair <int, int> > Graf[N + 1];
bitset <N+1> v(false);
int drum[N + 1], aparitii[N + 1];
int n, m;

void Add(int x, int y, int c)
{
    Graf[x].push_back(make_pair(y, c));
}

void Citire()
{
    int x, y, c;

    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        Add(x, y, c);
    }
}

void Init()
{
    for(int i = 2; i <= n; i++)
        drum[i] = INFINITY;
}

void BF()
{
    int nod, vecin, cost;

    Q.push(1);
    while(Q.empty() == 0)
    {
        nod = Q.front();
        Q.pop();
        v[nod] = true;
        if(aparitii[nod] > n)
        {
            fout << "Ciclu negativ!";
            return;
        }
        for(int i = 0; i < Graf[nod].size(); i++)
        {
            vecin = Graf[nod][i].first;
            cost = Graf[nod][i].second;
            if(drum[vecin] > drum[nod] + cost)
            {
                drum[vecin] = drum[nod] + cost;
                aparitii[vecin]++;
                if(v[vecin] == false)
                    Q.push(vecin);
            }
        }
    }
    for(int i = 2; i <= n; i++)
        fout << drum[i] << " ";
}

int main()
{
    Citire();
    Init();
    BF();
    return 0;
}