#include <fstream>
#include <queue>
#include <vector>
#define f first
#define s second
#define pinf 1000000007
#include <cstdlib>
using namespace std;

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

int n, m, x, y, c, viz[50005];
int d[50005];
queue < pair<int, int> > q;
vector < pair<int, int> > v[50005];
pair<int, int> mu;

void bf (int start)
{
    int i;

    for (i=1; i<=n; i++)
        d[i]=pinf;

    d[start]=0;
    viz[start]=1;

    for (auto it: v[start])
    {
        d[it.s]=it.f;
        q.push(it);
        viz[it.s]++;
    }

    while (q.empty()==0)
    {
        mu=q.front();
        q.pop();

        if (viz[mu.s]==n)
        {
            fout<<"Ciclu negativ!";
            exit(0);
        }
        else
        {
            for (auto it: v[mu.s])
            {
                if (d[mu.s]+it.f<d[it.s])
                {
                    d[it.s]=d[mu.s]+it.f;
                    q.push(make_pair(d[it.s], it.s));
                    viz[mu.s]++;
                }
            }
        }
    }
}

int main()
{
    int i;

    fin>>n>>m;

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

    bf(1);

    for (i=2; i<=n; i++)
    {
        fout<<d[i]<<" ";
    }

    fin.close();
    fout.close();
    return 0;
}