#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

#define pb push_back

using namespace std;

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

const int N = 5e4 + 10;
const int INF = INT_MAX;

int n, m;

struct graph
{
    int y, c, nr;
};

vector < graph > graf[N];

int dist[N];
queue < int > q;

int main()
{
    cin >> n >> m;

    graph g; int x;
    for(int i = 0; i < m; ++i)
    {
        cin >> x >> g.y >> g.c;
        g.nr = 0;
        graf[x].pb(g);
    }

    for(int i = 1; i <= n; ++i)
        dist[i] = INF;

    dist[1] = 0;

    q.push(1);

    while(q.size())
    {
        int cnod = q.front();

        for(int i = 0; i < graf[cnod].size(); ++i)
        {
            int nnod = graf[cnod][i].y;
            int ncost = graf[cnod][i].c;

            if(dist[cnod] + ncost < dist[nnod])
            {
                dist[nnod] = dist[cnod] + ncost;

                ++graf[cnod][i].nr;
                if(graf[cnod][i].nr > n-1)
                {
                    cout << "Ciclu negativ!";
                    return 0;
                }

                q.push(nnod);
            }
        }
        q.pop();
    }

    for(int i = 2; i <= n; ++i)
        cout << dist[i] << " ";

    return 0;
}