#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
queue<int>q;
int n, m, from, to, cost, nr_queue[50005], costuri[50005];
bool inqueue[50005];

vector<pair<int,int> >graph[50005];

void bellman_ford()
{
    q.push(1);
    inqueue[1]=true;
    nr_queue[1]++;
    while (!q.empty())
    {
        int el=q.front();
        q.pop();
        inqueue[el]=false;
        for (auto &v:graph[el])
        {
            if (costuri[el]+v.second<costuri[v.first])
            {
                costuri[v.first]=costuri[el]+v.second;
                if (!inqueue[v.first])
                {
                    inqueue[v.first]=true;
                    nr_queue[v.first]++;
                    q.push(v.first);
                    if (nr_queue[v.first]>n-1)
                    {
                        g << "Ciclu negativ!";
                        return;
                    }
                }
            }
        }
    }
    for (int i=2; i<=n; ++i)
        g << costuri[i] <<' ';
}

int main()
{
    f >> n >> m;
    for (int i=2; i<=n; ++i)
        costuri[i]=0x3f3f3f3f;
    for (int i=1; i<=m; ++i)
    {
        f >> from >> to >> cost;
        graph[from].push_back({to,cost});
    }
    bellman_ford();
    return 0;
}