#include <bits/stdc++.h>
#define NMAX 50005
#define INF 2000000000
using namespace std;
ifstream f ("bellmandford.in");
ofstream g ("bellmandford.out");

vector < pair < int, int > > a[NMAX];
bitset < NMAX > in_queue;
queue < int > q;
vector < int > dist(NMAX, INF), cnt(NMAX);
int n, m;

int main()
{
    f>>n>>m;
    while (m--)
    {
        int x, y, c;
        f>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
    }
    q.push(1);
    in_queue[1] = 1;
    dist[1] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        in_queue[x] = 0;
        for (unsigned i = 0; i < a[x].size(); i++)
        {
            if (dist[a[x][i].first] > dist[x] + a[x][i].second)
            {
                if (!in_queue[a[x][i].first])
                {
                    if (cnt[a[x][i].first] > n)
                    {
                        g<<"Ciclu negativ\n";
                        return 0;
                    }
                    dist[a[x][i].first] = dist[x] + a[x][i].second;
                    q.push(a[x][i].first);
                    in_queue[a[x][i].first] = 1;
                    cnt[a[x][i].first]++;
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        g<<dist[i]<<' ';
    return 0;
}