#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int INF=250000001;

struct muchie
{
    int y,c;
};

vector <muchie> lista[50001];
queue <int>q;
int dist[50001],f[50001];
int n,m;

int bellford(int nod)
{
    dist[nod]=0;
    q.push(nod);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(dist[x]!=INF)
        {
            for(auto k:lista[x])
            {
                int y=k.y;
                int c=k.c;
                if(dist[x]+c<dist[y])
                    {
                        dist[y]=dist[x]+c;
                        f[y]++;
                        if(f[y]==n)
                         return false;
                        q.push(y);
                    }
            }
        }
    }
    return true;
}

int main()
{
    int x,y,c;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        lista[x].push_back({y,c});
    }
    
    for(int i=1;i<=n;i++)
        dist[i]=INF;
        
    bool rasp=bellford(1);
    if(rasp==false)
        cout<<"Ciclu negativ!";
    else
    {
        for(int i=2;i<=n;i++)
            cout<<dist[i]<<" ";
    }
    
    return 0;
}