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

using namespace std;

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

int n,m,viz[NMAX],dist[NMAX];
vector <pair<int,int>> g[NMAX];
queue <int> q;

void init()
{
    for(int i = 2; i < NMAX; ++i)
        dist[i] = INF;
}

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

bool ok = 1;

void bellmanford()
{
    q.push(1);
    while(not q.empty())
    {
        int nod = q.front();
        q.pop();

        if(viz[nod] >= n)
        {
            ok = 0;
            return;
        }

        for(vector<pair<int,int>>::iterator it = g[nod].begin(); it != g[nod].end(); ++it)
            if(dist[it->first] > dist[nod] + it->second)
            {
                dist[it->first] = dist[nod] + it->second;
                q.push(it->first);
                ++viz[it->first];
            }
    }
}

void output()
{
    if(ok)
        for(int i = 2; i <= n; ++i)
            o << dist[i] << ' ';
    else
        o << "Ciclu negativ!\n";
}

int main()
{
    init();
    input();
    bellmanford();
    output();
    return 0;
}