#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");

using namespace std;

const int oo = 0x3f3f3f3f;

struct strct
{
    int nod,cost;
};
struct crit
{
    bool operator()(strct a,strct b)
    {
        return a.cost < b.cost;
    }
};
priority_queue<strct,vector<strct>,crit> pq;
vector<vector<pair<int,int>>> G;
vector<int> dist,IQ;
bool ok = true;
int n,m;

void read()
{
    int x,y,c;

    fin >> n >> m;
    G.resize(n+1);
    dist.resize(n+1,oo);
    IQ.resize(n+1,1);

    for(int i = 0 ; i < m; ++i)
    {
        fin >> x >> y >> c;
        G[x].push_back({y,c});
       // G[y].push_back({x,c});
    }
}
void Dijkstra_Bellman(int start)
{
    pq.push({start,0});
    dist[start] = 0;
    while(!pq.empty() && ok)
    {
        strct crt = pq.top();
        pq.pop();
        for(auto vecin : G[crt.nod])
            if(dist[vecin.first] > dist[crt.nod] + vecin.second)
            {
                IQ[vecin.first]++;
                dist[vecin.first] = dist[crt.nod] + vecin.second;
                pq.push({vecin.first, dist[vecin.first]});
                if(IQ[vecin.first] > n)
                    ok = false;
            }
    }
}
int main()
{
    read();
    Dijkstra_Bellman(1);
    if(ok)
        for(int i = 2; i <= n; ++i)
            fout << dist[i] << ' ';
    else
        fout << "Ciclu negativ!";
    return 0;
}