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

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

const int Inf = 0x3f3f3f3f;
vector<vector<pair<int, int>>> G;
vector<int> d,N,v;
int n, m;

void Read_Graph()
{
    int x,y,w;
    fin >> n >> m;
    G.resize(n+1);
    v.resize(n+1);
    for (int i = 1;i <= m; i++)
    {
        fin >> x >> y >> w;
        G[x].push_back({y,w});
    }

}

void Bellmanford(int x,vector<int> &d)
{   queue<int> Q;
    d=vector<int> (n+1,Inf);
    N=vector<int> (n+1 );

    v[x] = 1;
    d[x] = 0;


    for( Q.push(x);!Q.empty();Q.pop())
    {
        x = Q.front();
        v[x] = 0;

        for (auto & p :G[x])
        {
            int y = p.first;
            int w = p.second;
            if (d[y] > d[x] + w)
                  {
                    d[y] = d[x] + w;
                    if (!v[y])
                         {
                            N[y]++;
                            if (N[y] == n)
                                {
                                fout<<"Ciclu negativ!";
                                return ;
                                }
                    Q.push(y);
                    v[y] = 1;
                          }
                 }
        }
    }


}
int main()
{
Read_Graph();
Bellmanford(1,d);
for (int i = 2; i <= n; i++)
        fout << d[i] << " ";

    return 0;
}