#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define inf 1000000000
#define MAX_N 50001
#define MAX_M 250001
using namespace std;
struct muchie
{
    int i,j,c;
}e[MAX_M];
long cost[MAX_N],n,m,i,j,k,left,right;
bool use[MAX_N];
vector<long> v[MAX_N];
vector< pair<long,long> > h;
void init()
{
    for(int i=1;i<=n;i++)
        cost[i]=inf;
    cost[1]=0;
    h.push_back(make_pair(0,1));
    make_heap(h.begin(),h.end());
}
void solve()
{
    pair<long,long> per;
    long j,nod,poz;
    long long pas=0;
    while(h.size()&&pas<=(long long)n*m)
    {
        cout<<"in ";
        pas++;
        pop_heap(h.begin(),h.end());
        per=h.back();
        h.pop_back();
        nod = per.second;
        for(j=0;j<(int)v[nod].size();j++)
        {
            poz = v[nod][j];
            if(cost[e[poz].i]+e[poz].c<cost[e[poz].j])
            {
                cost[e[poz].j]=cost[e[poz].i]+e[poz].c;
                if(!use[e[poz].j])
                {
                    use[e[poz].j]=true;
                    h.push_back(make_pair(-cost[e[poz].j],e[poz].j));
                    push_heap(h.begin(),h.end());
                }
            }
        }
    }
}
bool ciclu_negativ()
{
    for(int i=1;i<=m;i++)
        if(cost[e[i].i]+e[i].c<cost[e[i].j])
            return true;
    return false;
}
int main()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>e[i].i>>e[i].j>>e[i].c;
        v[e[i].i].push_back(i);
    }
    init();
    solve();
    ofstream g("bellmanford.out");
    if(ciclu_negativ())
    {
        g<<"Ciclu Negativ!\n";
    }
    else
        for(int i=2;i<=n;i++)
            g<<cost[i]<<" ";
    return 0;
}