#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define NMAX 500002

using namespace std;

ifstream f("bellmanford.in");
ofstream o("bellmanford.out");

int n,m;
vector <pair<int,int>> g[NMAX];
int dist[NMAX], ap[NMAX], dist2[NMAX];

void citire()
{
    f >> n >> m;
    for(int i = 1; i <= n; ++i)
        g[0].push_back({i,0});
    int x,y, c;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        g[x].push_back({y,c});
    }
}

bool bellman_ford()
{
    queue <int> q;
    for(int i = 1; i <= n; ++i)
        dist[i] = INF;

    q.push(0);
    while(not q.empty())
    {
        int nod = q.front();
        q.pop();

        ap[nod] ++;
        if(ap[nod] >= n)
            return false;

        for(auto i: g[nod])
            if(dist[i.first] > dist[nod] + i.second)
            {
                dist[i.first] = dist[nod] + i.second;
                q.push(i.first);
            }
    }

    return true;
}

void reponderare()
{
    for(int i = 1; i <= n; ++i)
    {
        for(auto &j : g[i])
        {
            j.second += dist[i] - dist[j.first];
        }

    }
}

void dijkstra()
{
    for(int i = 1; i <= n; ++i)
        {
            dist2[i] = dist[i];
            dist[i] = INF;
        }
    dist[1] = 0;

    priority_queue<pair<int,int>> q;
    q.push({0,1});
    while(not q.empty())
    {
        int nod = q.top().second;
        int cost = -q.top().first;
        q.pop();

        if(cost != dist[nod])
            continue;
        for(auto i: g[nod])
            if(dist[i.first] > dist[nod] + i.second)
            {
                dist[i.first] = dist[nod] + i.second;
                q.push({-dist[i.first],i.first});
            }
    }
}

void afish()
{
    for(int i = 2; i <= n; ++i)
        o << dist[i] + dist2[i] - dist2[1] << ' ';
}

int main()
{
    citire();
    if(bellman_ford())
    {
        reponderare();
        dijkstra();
        afish();
    }
    else
    {
        o << "Ciclu negativ!\n";
    }
    return 0;
}