#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <bitset>
#define NMax 50005
#define INF 1<<28
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
std::vector< std::pair<int,int> > G[NMax];
std::vector<int> nodes(NMax);
std::bitset<NMax> viz;
std::queue< std::pair<int,int> > coada;
int n,m,nod1,nod2,cost,d[NMax],xyz[10][10][10];
bool Bellman_Ford(int x)
{
    for(int i=2;i<=n;++i)d[i] = INF;
    d[x] = 0;viz[x] = 1;
    coada.push(std::make_pair(x,0));
    while(coada.empty()==0)
    {
        int val = (coada.front()).second;
        int nod = (coada.front()).first;
        coada.pop();
        ++nodes[nod];
        viz[nod] = 0;
        if(nodes[nod]==n)return 0;
        for(int i=0;i<G[nod].size();++i)
        {
            if(d[(G[nod][i]).first] > val + (G[nod][i]).second)
            {
                d[(G[nod][i]).first] = val + (G[nod][i]).second;
                coada.push(std::make_pair((G[nod][i]).first,d[(G[nod][i]).first]));
                if(viz[(G[nod][i]).first]==0)
                {
                    viz[(G[nod][i]).first]=1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>nod1>>nod2>>cost;
        G[nod1].push_back(std::make_pair(nod2,cost));
    }
    if(Bellman_Ford(1)==0)fout<<"Ciclu negativ!";
    else
    {
        for(int i=2;i<=n;++i)fout<<d[i]<<" ";
    }
    return 0;
}