#include <bits/stdc++.h>

#define oo 0x3f3f3f3f
#define edge pair<int, int>
#define nod first
#define cost second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
int x, y, cost;
bool viz[50005];
int nr [50005];
int dist[500005];
vector<edge> graf[50005];

void Read()
{
    f>>n>>m;
    for(int i = 1;i <= m;++i)
    {
        f>>x>>y>>cost;
        graf[x].push_back({y, cost});
    }
}

void Bellman_Ford()
{
    for(int i = 2;i <= n;++i)
        dist[i] = oo;
    queue<int> q;
    q.push(1);
    viz[1] = true;

    while(!q.empty())
    {
        int nod = q.front();


        for(vector<edge>::iterator it = graf[nod].begin();it != graf[nod].end();++it)
            if(dist[(*it).nod] > dist[nod] + (*it).cost)
            {
                dist[(*it).nod] = dist[nod] + (*it).cost;
                if(!viz[(*it).nod]) q.push((*it).nod);
                viz[(*it).nod] = true;
                nr[(*it).nod]++;
                if(nr[(*it).nod] >= n)
                {
                    g<<"Ciclu negativ!";
                    exit(0);
                }
            }

        q.pop();
        viz[nod] = false;
    }
}

int main()
{
    Read();
    Bellman_Ford();
    for(int i = 2;i <= n;++i)
        g<<dist[i]<<" ";
    return 0;
}