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

using namespace std;

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

int n, m;
int dist[50005];
bool used[50005];
vector < pair < int, int > > v[50005];
queue < int > coada;

const int INF = 2147483647;

void BellmanFord (int start)
{
    for (int i=2; i<=n; i++)
        dist[i] = INF;

    coada.push(start);
    while (!coada.empty())
    {
        int nod = coada.front();
        int lg = v[nod].size();
        coada.pop();

        for (int i=0; i<lg; i++)
        {
            if (!used[v[nod][i].first])
            {
                if (dist[v[nod][i].first] == INF)
                {
                    used[v[nod][i].first] = 1;
                    dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
                    coada.push(v[nod][i].first);
                }
                else if (dist[nod] + v[nod][i].second < dist[v[nod][i].first])
                {
                    dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
                    coada.push(v[nod][i].first);
                }
            }
        }
    }
}

bool Check (int start)
{
    bool gasit = false;
    memset(used, 0, sizeof(used));
    used[start] = 1;
    coada.push(start);

    while (!coada.empty() && !gasit)
    {
        int nod = coada.front();
        int lg = v[nod].size();
        used[nod] = 1;
        coada.pop();

        for (int i=0; i<lg; i++)
        {
            if (!used[v[nod][i].first])
            {
                if (dist[nod] + v[nod][i].second < dist[v[nod][i].first])
                    gasit = true;
                coada.push(v[nod][i].first);
            }
        }
    }
    if (gasit)
      return true;
    return false;
}

void Print ()
{
    for (int i=2; i<=n; i++)
        g << dist[i] << " ";
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y, cost;
        f >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
    }

    BellmanFord(1);
    if (!Check(1)) Print();
    else g << "Ciclu negativ!";

    return 0;
}