#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define inf 1000000
#include<utility>
#define l vector<pair<int,int> > ::iterator
#define NMAX 50001
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,ap[NMAX],dmin[NMAX];
vector<pair<int,int> > g[NMAX];
vector<bool>viz(NMAX,false);
queue<int>q;
void read()
{
    fin>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
    fin.close();
}

void bellmanford(int x)
{
    viz[x]=true;
    q.push(x);
    dmin[x]=0;
    while(!q.empty())
    {
        x=q.front();q.pop();
        viz[x]=false;
        for(l it=g[x].begin();it!=g[x].end();it++)

            if(dmin[it->first]>dmin[x]+it->second)
                {dmin[it->first]=dmin[x]+it->second;
            if(!viz[it->first])
            {
                viz[it->first]=true;
                q.push(it->first);
                if(++ap[it->first]>n)
                {
                    fout<<"Ciclu negativ!";
                    return;
                }
            }}

    }
    for(int i=2;i<=n;i++)
    fout<<dmin[i]<<" ";
}
int main()
{
    read();
    for(int i=1;i<=n;i++)dmin[i]=inf,ap[i]=0;
    bellmanford(1);
    fout.close();
    return 0;
}