#include <fstream>
#include <queue>
#define infinit 1>>19

using namespace std;

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

queue<int> Q;
int n,d[50001],nr,i,it[50001];
bool viz[50001],ok;


struct nod{
    int info;
    int cost;
    nod* leg;
};

nod *p, *l[50001];

void BellmanFord(int x)
{
    int i;
    nod *p;

    for(i = 1; i <= n; ++i)
        d[i] = 1<<19;
    d[x] = 0;
    viz[x]=1;

    Q.push(x);

    while(Q.size())
    {
        x=Q.front();
        Q.pop();
        viz[x] = 0;
        for(p = l[x]; p != NULL; p = p->leg)
        {
            if(d[p->info]>d[x]+p->cost)
                    {
                        d[p->info] = d[x]+p->cost;

            if(!viz[p->info])
                {
                    if(++it[p->info]>n)
                    {
                        fout << "Ciclu negativ!";
                        ok = 1;
                        break;
                    }
                    Q.push(p->info);
                    viz[p->info] = 1;
                }
                    }
        }
        if(ok)
            break;
    }



}
void citire()
{
    int i, x, y, m, g;
    nod *p;
    fin >> n >> m ;

    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y >> g;
        p = new nod;
        p -> info = y;
        p -> leg = l[x];
        p -> cost = g;
        l[x] = p;

    }
}

int main()
{

    citire();
    BellmanFord(1);
    if(!ok)
        for(i = 2; i <=n; ++i)
            fout << d[i] << " ";
    return 0;
}