#include<fstream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
#define INF 1<<30
#define nMAX 50005
#define mMAX 250005

typedef struct muchie
{
    long a;
    long b;
    long c;
};
muchie e[mMAX];

int N,M,i,j,k,cost[nMAX],f[nMAX];
vector<long> v[nMAX];
vector< pair<long,long> > h;

void init();
void solve();
long check_negativ();

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    in>>N>>M;
    for(i=1;i<=M;i++)
    {
        in>>e[i].a>>e[i].b>>e[i].c;
        v[e[i].a].push_back(i);
    }
    init();
    solve();
    if(check_negativ())
    {
        out<<"Ciclu negativ!\n";
        return 0;
    }
    for(i=2;i<=N;i++)
        out<<cost[i]<<" ";
    return 0;



    return 0;
}

void init()
{
    long i;
    cost[1]=0;
    for(i=2;i<=N;i++)
        cost[i]=INF;
    h.push_back(make_pair(0,1));
    make_heap(h.begin(),h.end());
}

void solve()
{
    pair<long,long> per;
    long i, j, nod, poz;
    long long pas=0;
    while(h.size()) && pas<=1LL*N*M)
    {
        pas++;
        pop_heap(h.begin(),h.end());
        per=h.back();
        h.pop_back();
        nod=per.second;
        f[nod]=0;
        for(j=0;j<v[nod].size();j++)
        {
            poz=v[nod][j];
            if(cost[e[poz].a]+e[poz].c<cost[e[poz].b])
            {
                cost[e[poz].b]=cost[e[poz].a]+e[poz].c;
                if(!f[e[poz].b])
                {
                    f[e[poz].b]=1;
                    h.push_back(make_pair(-cost[e[poz].b],e[poz].b));
                    push_heap(h.begin(),h.end());

                }
            }
        }
    }
}

long check_negativ()
{
    long i;
    for(i=1;i<=M;i++)
        if(cost[e[i].a]+e[i].c < cost[e[i].b])
            return 1;
    return 0;


}