#include <bits/stdc++.h>
#define mp make_pair
#define INF (1<<30)

using namespace std;

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

int n, m, ver[50001], dist[50001];
vector < pair <int, int> > v[50001];
queue < pair<int, int> > q;
bool inCoada[50001];
bool Bellmanford()
{
    q.push(mp(1, 0));
    for(int i = 2; i <= n; i++)
        dist[i] = INF;

    while(!q.empty())
    {
        int nod = q.front().first;
        int last = q.front().second;
        ver[nod]++;
        if(ver[nod] >= n)
        {
            //fout << "Ciclu negativ!";
            return false;
        }
        q.pop();
        inCoada[nod] = 0;
        for(int i = 0; i < v[nod].size(); i++)
        {
            int nod_urm, cost;
            nod_urm = v[nod][i].first;
            cost = v[nod][i].second;
            if(dist[nod] +cost < dist[nod_urm])
              {
                  dist[nod_urm] = dist[nod]+cost;
                   q.push(mp(nod_urm, nod));
              }
        }

    }
    return true;
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back(mp(b, c));
       // v[b].push_back(mp(a,c));
    }


    if(Bellmanford())
    for(int i = 2; i <= n; i++)
        fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";
    return 0;
}