#include <bits/stdc++.h>
#define NMAX 50005
#define INF 2000000000
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.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++)
        {
            pair < int, int > p = a[x][i];
            if (dist[p.first] > dist[x] + p.second)
            {
                dist[p.first] = dist[x] + p.second;
                if (!in_queue[p.first])
                {
                    if (cnt[p.first] > n)
                    {
                        g<<"Ciclu negativ!\n";
                        return 0;
                    }
                    q.push(p.first);
                    in_queue[p.first] = 1;
                    cnt[p.first]++;
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        g<<dist[i]<<' ';
    return 0;
}