#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const long long inf=1LL<<50;
const int maxn=50010;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
long long N,M,d[maxn],q[maxn];
vector <long long>a[maxn],c[maxn];
vector <pair <long,long> >h;

void Bellman_Ford()
{
    long long i, nod, next;
    long long pas=0;

    d[1]=0;
    for(i=2; i<=N; i++) d[i]=inf;

    h.push_back(make_pair(0, 1));
    make_heap(h.begin(), h.end());

    while(!h.empty() && pas<=1LL*N*M)
    {
        pas++;
        nod=h[0].second;
        pop_heap(h.begin(), h.end());
        h.pop_back();
        q[nod]=0;
        for(i=0; i<a[nod].size(); i++)
        {
            next=a[nod][i];
            if(d[next]>d[nod]+c[nod][i])
            {
                d[next]=d[nod]+c[nod][i];
                if(q[next]==0)
                {
                    q[next]=1;
                    h.push_back(make_pair(-d[next], next));
                    push_heap(h.begin(), h.end());
                }
            }
        }
    }
}
long check_negativ()
{
    long i,j;
    for (i=1;i<=N;i++)
        for (j=0;j<a[i].size();j++)
            if (d[i]+c[i][j]<d[a[i][j]]) return 1;
    return 0;
}

int main()
{
    int i,x,y,z;
    f>>N>>M;
    for (i=1;i<=M;i++)
    {
        f>>x>>y>>z;
        a[x].push_back(y);
        c[x].push_back(z);
    }
    Bellman_Ford();
    if(check_negativ()==1)
    {
        g<<"Ciclu negativ!";
        return 0;
    }
    for (i=2;i<=N;i++)
        g<<d[i]<<" ";
    return 0;

}