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

#define u_int unsigned int

using namespace std;

const int infinit = 1 << 30;

struct muchie
{
    u_int y;
    int d;
};

vector<muchie> noduri[50001];
int cost[50001];
bool viz[50001];
u_int ciclu[50001];

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    u_int n, m;
    fin >> n >> m;
    for(u_int i = 1; i <= m; ++i)
    {
        int a, b, c;
        fin >> a >> b >> c;
        muchie arc;
        arc.y = b;
        arc.d = c;
        noduri[a].push_back(arc);
    }
    u_int s = 1;
    for(u_int i = 1; i <= n; i++)
    {
        cost[i] = infinit;
    }
    queue<u_int> coada;
    coada.push(s);
    cost[s] = 0;
    while(!coada.empty())
    {
        u_int x = coada.front();
        coada.pop();
        viz[x] = 0;
        for(u_int i = 0; i < noduri[x].size(); i++)
        {
            int drum = cost[x] + noduri[x][i].d;
            if(drum < cost[noduri[x][i].y])
            {
                cost[noduri[x][i].y] = drum;
                if(viz[noduri[x][i].y] == 0)
                {
                    viz[noduri[x][i].y] = 1;
                    coada.push(noduri[x][i].y);
                }
                ++ciclu[noduri[x][i].y];
                if (ciclu[noduri[x][i].y] > n)
                {
                    fout << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(u_int i = 1; i <= n; i++)
    {
        if(i != s)
        {
            if(cost[i] != infinit)
                fout << cost[i] << ' ';
                else
                    fout << 0 << ' ';
        }
    }
    return 0;
}