#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int dim=5e4+10;
const int oo=2e9;
typedef long long ll;
typedef pair<int,int> pi;
int t,T,n,m,a,b,c;

vector < pi > V[dim];
vector < int > d(dim,oo);

struct cmp
{
    bool operator()(int x,int y)
    {
        if(d[x]<d[y])
            return 1;
        else
        {
            if(d[x]==d[y])
                return (x<y);
            else
                return 0;
        }
    }
};

set < int,cmp > S;
set < int,cmp > ::iterator it;

void Dijkstra()
{
    S.insert(1);
    d[1]=0;
    while(!S.empty())
    {
        int nod=*(S.begin());
        S.erase(S.begin());
        for(pi x:V[nod])
        {
            int vecin=x.first;
            int cost=x.second;
            if(d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                it=S.find(vecin);
                if(it!=S.end())
                    S.erase(it);
                S.insert(vecin);
            }
        }
    }
}


bool Dijkstra2()
{
    vector < int > viz(dim,0),rep(dim,0);
    queue < int > qu;
    qu.push(1);
    viz[1]=1;
    d[1]=0;
    while(!qu.empty())
    {
        int nod=qu.front();
        qu.pop();
        viz[nod]=0;
        rep[nod]++;
        if(rep[nod]==n)
        {
            return 0;
        }
        for(pi x:V[nod])
        {
            int vecin=x.first;
            int cost=x.second;
            if(d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                if(!viz[vecin])
                {
                    viz[vecin]=1;
                    qu.push(vecin);
                }
            }
        }
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[a].pb({b,c});
    }
    if(Dijkstra2()==0)
    {
        g<<"Ciclu negativ!";
        return 0;
    }
    for(int i=2;i<=n;i++)
    if(d[i]==oo) g<<0<<' ';
    else g<<d[i]<<' ';

    return 0;
}