#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int oo=1000000000,nmax=50001;
int n,m,nrq[nmax],d[nmax];
bool inq[nmax];
vector <pair<int,int> > v[nmax];
void citire()
{
    in>>n>>m;
    int i,x,y,cost;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
}
int bellmanford()
{
    int i,ok=1,j;
    for(i=2;i<=n;i++)
        d[i]=oo;
    queue <int> q;
    q.push(1);
    inq[1]=1;
    nrq[1]=1;
    while(!q.empty() && ok!=0)
    {
        i=q.front();
        inq[i]=0;
        q.pop();
        for(j=0;j<v[i].size();j++)
        {
            int vecin=v[i][j].first,cost=v[i][j].second;
            {
                if(d[vecin]>d[i]+cost)
                {
                    d[vecin]=d[i]+cost;
                    if(inq[vecin]==0)
                    {
                        q.push(vecin);
                        nrq[vecin]++;
                        inq[vecin]=1;
                        if(nrq[vecin]>n)
                            ok=0;
                    }
                }
            }
        }
    }
    return ok;

}
void afisare()
{
    for(int i=2;i<=n;i++)
        out<<d[i]<<" ";
}
int main()
{
    citire();
    if(bellmanford()==0)
        out<<"Ciclu negativ!";
    else
        afisare();
    return 0;
}