#include <fstream>
#include <string.h>
#include <vector>
#include <queue>
#define MAX 50005
#define INF 0x3f3f3f3f

using namespace std;

int n, m, ok;
int d[MAX], a[MAX];
vector < pair <int, int> > v[MAX];
queue <int> q;

void read ()
{
    ifstream f("bellmanford.in");
    int x, y, c;

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

    f.close();
}

void bellmanford ()
{
    int x, y, c;
    while (ok && !q.empty() )
    {
        x = q.front();
        q.pop();
        for (int i = 0; i < v[x].size(); i ++ )
        {
            y = v[x][i].first, c = v[x][i].second;
            if ( d[x] + x < d[y] )
            {
                d[y] = d[x] + c;
                a[y] ++;
                q.push(y);
                if ( a[y] > n )
                    ok = 0;
            }
        }
    }
}

void solve ()
{
    memset(d, INF, sizeof(d));
    d[1] = 0;
    q.push(1);
    a[1] = 1;
    ok = 1;
    bellmanford();
}

void write ()
{
    ofstream g("bellmanford.out");

    if ( ok == 0 )
        g << "Ciclu negativ!";
    else for (int i = 2; i <= n; i ++ )
        g << d[i] << " ";
    g << '\n';

    g.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}