#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#include <bitset>
#define NMAX 50005
#define INF 1<<30
using namespace std;

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

bitset<NMAX> inCoada;
vector<pair<int, int> > G[NMAX];
vector<int> cmin(NMAX,INF), frecvCoada(NMAX,0);
queue<int> Q;
int N,M;
bool cicluNegativ = false;

void BellmanFord(int x);

int main()
{
    int i,x,y,c;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }

    BellmanFord(1);

    if(cicluNegativ)
        fout<<"Ciclu negativ!";
    else
        for(i = 2; i<=N;i++)
            fout<<cmin[i]<<" ";
    fout<<'\n';
    return 0;
}

void BellmanFord(int x)
{
    Q.push(x);
    inCoada[x] = true;
    cmin[x] = 0;

    while(!Q.empty() && !cicluNegativ)
    {
        int nod = Q.front();
        Q.pop();
        inCoada[nod] = false;

        for(int i = 0; i<G[nod].size();i++)
            if(cmin[nod] < INF && cmin[nod] + G[nod][i].second  < cmin[G[nod][i].first])
            {
                cmin[G[nod][i].first]= cmin[nod] + G[nod][i].second;
                if(!inCoada[G[nod][i].first])
                {
                    if(frecvCoada[G[nod][i].first] >= N)
                        cicluNegativ = true;
                    else
                    {
                        inCoada[G[nod][i].first] = true;
                        Q.push(G[nod][i].first);
                        frecvCoada[G[nod][i].first]++;
                    }

                }
            }
    }
}