#include <bits/stdc++.h>

using namespace std;


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

//ifstream in("dijkstra.in");
//ofstream out("dijkstra.out");

vector<pair<int,int>> la[50005];

int dmin[50005],viz[50005];
bool negativ;

void BellmanFord(int nod_start, int n)
{
    dmin[nod_start]=0;

    priority_queue<pair<int,int>> pq;
    pq.push({0,nod_start});

    while(pq.empty() != true)
    {
        int nod_curent = pq.top().second;
        viz[nod_curent]++;
        if(viz[nod_curent]>=n)
        {
            negativ=1;
            out<<"Ciclu negativ!";
            return;
        }
        pq.pop();
       // if(viz[nod] == 0)
       // {
            viz[nod_curent] = 1;
            for(auto nod_vecin : la[nod_curent])
            {
                if(dmin[nod_vecin.first] > dmin[nod_curent]+nod_vecin.second)
                {
                    dmin[nod_vecin.first] = dmin[nod_curent] + nod_vecin.second;
                    pq.push({-dmin[nod_vecin.first],nod_vecin.first});
                }
            }
        //}
    }
}

int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1; i<=n; i++)
        dmin[i]=INT_MAX;

    for(int i=1; i<=m; i++)
    {
        int x,y,w;
        in>>x>>y>>w;
        la[x].push_back({y,w});
    }

    BellmanFord(1,n);

    if(!negativ)
    for(int i=2; i<=n; i++)
    {
        if(dmin[i] == INT_MAX)
            out<<0<<" ";
        else
            out<<dmin[i]<<" ";
    }
    return 0;

}