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

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int N = 50005;
const int INFINIT = 250000005;

struct muchie
{
    int nod, cost;
};
vector <muchie> g[N];
queue <int> coada;
bool eincoada[N];
int nrviz[N], d[N];
//d[i] = dist de la 1 la i;
int main()
{
    int n, m, i, a, b, c;
    in >> n >> m;
    for(i = 1; i <= m; i++)
    {
        in >> a >> b >> c;
        g[a].push_back({b,c});
    }
    coada.push(1);
    eincoada[1] = true;
    nrviz[1] = 1;
    for(i = 2; i <= n; i++)
        d[i] = INFINIT;
    while(!coada.empty())
    {
        int node = coada.front();
        coada.pop();
        eincoada[node] = false;
        for(i = 0; i < g[node].size(); ++i)
            if(d[g[node][i].nod] > d[node] + g[node][i].cost)
            {
                d[g[node][i].nod] = d[node] + g[node][i].cost;
                if(eincoada[g[node][i].nod] == false)
                {
                    eincoada[g[node][i].nod] = true;
                    coada.push(g[node][i].nod);
                }
                nrviz[g[node][i].nod] ++;
                if(nrviz[g[node][i].nod] > n)
                {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }

    }
    for(i = 2; i <= n; i++)
        out <<d[i]<<" ";
    return 0;
}