//BELLMAN FORD optimizat cu heap
#include<iostream>
#include<fstream>
#include<vector>
#include<limits>
#include<set>

#define pb push_back
#define mkp make_pair
#define DMAX 50005
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


const int INF=numeric_limits<int>::max()/2;
vector<vector<pair<int,int> > > G(DMAX);
multiset<pair<int,int> > H;
int D[DMAX];
int ap[DMAX];
bool inH[DMAX];
int n,m;
bool OKc=true;
void BellmanFord(int start);

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int p,d,c;
        f>>p>>d>>c;
        G[p].pb(mkp(d,c));
    }
    BellmanFord(1);
    if(OKc==true)
        for(int i=2;i<=n;i++)
            g<<D[i]<<" ";
    else
        g<<"Ciclu negativ!";
    return 0;
}

void BellmanFord(int start)
{
    for(int i=1;i<=n;i++)
    {
        D[i]=INF;
        ap[i]=0;
    }
    D[start]=0;
    inH[start]=true;
    H.insert(mkp(D[start],start));
    while(!H.empty())
    {
        int nodc=H.begin()->second;
        H.erase(H.begin());
        inH[nodc]=false;
        for(vector<pair<int,int> >::iterator it=G[nodc].begin();it!=G[nodc].end();it++)
            if(D[it->first]>D[nodc]+it->second)
            {
                if(inH[it->first]==false)
                {
                    H.insert(mkp(it->second,it->first));
                    ap[it->first]++;
                }
                D[it->first]=D[nodc]+it->second;
                if(ap[it->first]>n) H.clear();
            }
    }

    for(int i=1;i<=n;i++)
        for(vector<pair<int,int> >::iterator it=G[i].begin();it!=G[i].end();it++)
            if(D[it->first]>D[i]+it->second) OKc=false;

}