#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50005;
const int INF = 1 << 29;

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


int n;
vector<int> vecini[MAXN];
vector<int> cost[MAXN];
int d[MAXN];
bool ciclu_negativ = false;

void citire()
{
    int m;
    in >> n >> m;
    int a,b,c;
    for (int i = 1;i <= m;++i)
    {
        in >> a >> b >> c;
        vecini[a].push_back(b);
        cost[a].push_back(c);
    }
}

void bellmanford()
{
    queue<int> q;
    bool in_coada[MAXN];
    int vizite[MAXN];
    q.push(1);
    in_coada[1] = true;
    for (int i = 1;i <= n;++i)
    {
        d[i] = INF;
        vizite[i] = 0;
    }
    vizite[1] = 1;
    d[1] = 0;

    while (!q.empty() && !ciclu_negativ)
    {
        int nod = q.front();
        int c,vecin;
        q.pop();
        in_coada[nod] = false;
        for (int i = 0;i < vecini[nod].size();++i)
        {
            vecin = vecini[nod][i];
            c = cost[nod][i];
            int dist = d[nod] + c;
            if (dist < d[vecin])
            {
                d[vecin] = dist;
                if (!in_coada[vecin])
                {
                    if (vizite[vecin] > n)//detectare ciclu negativ
                        ciclu_negativ = true;
                    else
                    {
                        q.push(vecin);
                        in_coada[vecin] = true;
                        ++vizite[vecin];
                    }
                }
            }
        }
    }
}

int main()
{
    citire();
    bellmanford();
    if (ciclu_negativ)
        out << "Ciclu negativ!\n";
    else
    {
        for (int i = 2;i < n;++i)
            out << d[i] << " ";
        out << d[n] << "\n";
    }
    return 0;
}