#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
const int inf = 1e9;
vector < pair<int,int> > g[nmax];
queue<int> C;
int dmin[nmax],nr[nmax];
int n,m;
queue<int> c;
void citire()
{
    pair<int,int> aux;
    fin >> n >> m;
    int x,y,c;
    while (fin >> x >> y >> c)
    {
        //adaug pe y in lista de adiacenta a lui x
        /*G[x][lg[x]].vf = y;
        G[x][lg[x]].c = c;
        lg[x]++;*/
        aux.first = y;
        aux.second = c;
        g[x].push_back(aux);
    }
}
void bellman_ford()
{
    int i,x;
    bool negativ = false;
    for (i=1;i<=n;i++)
        dmin[i] = inf;
    dmin[1] = 0;
    C.push(1);
    while (!C.empty() && !negativ)
    {
        x = C.front();
        C.pop();
        for (auto e:g[x])
        {
            if (dmin[e.first] > dmin[x] + e.second)
            {
                dmin[e.first] = dmin[x] + e.second;
                nr[e.first]++;
                C.push(e.first);
                if (nr[e.first]>n)
                    negativ = true;
            }
        }
    }
    if (negativ==true)
        fout << "Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            fout << dmin[i] << ' ';
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    citire();
    bellman_ford();
    return 0;
}