#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int MAX=50005;
vector <pair<int,int> > a[MAX];
vector <pair<int,int> >::iterator it;
queue <int> c;
int n,m,x,y,cost,i,d[MAX],viz[MAX];
int main()
{
    f>>n>>m;
    for(i=1 ; i<=m ; ++i)
    {
        f>>x>>y>>cost;
        a[x].push_back(make_pair(y,cost));
    }

    for(i=2 ; i<=n ; ++i)
        d[i]=50000005;

    c.push(1);
    while(!c.empty())
    {
        x=c.front();
        viz[x]++;

        if(viz[x]==n)
        {
            g<<"Ciclu negativ!\n";
            return 0;
        }

        for(it=a[x].begin(); it!=a[x].end() ; ++it)
            if(d[x]+it->second<d[it->first])
            {
                d[it->first]=d[x]+it->second;
                c.push(it->first);
            }
        c.pop();
    }

    for(i=2 ; i<=n ; ++i)
        g<<d[i]<<" ";
    g<<'\n';
    return 0;
}