#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <cstdlib>
using namespace std;
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
#define MaxN 50001
#define INF 0x3f3f3f3f
 
vector<pair<int,int> > G[MaxN];
vector<int> d(MaxN), cntinQ(MaxN);
bitset<MaxN> inQueue;
queue<int> Q;
 
int n, m;
int x,y,z;
 
void Read();
void Bf();
 
int main()
{
    Read();
    Bf();
 
    fin.close();
    fout.close();
    return 0;
}
 
void Bf()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = INF;
 
    d[1] = 0;
    Q.push(1);
    inQueue[1] = 1;
 
    while ( !Q.empty() )
    {
        int nod = Q.front();
        Q.pop();
        inQueue[nod] = 0;
 
        for ( auto p : G[nod] )
        {
            if ( d[p.first] > d[nod] + p.second )
            {
                d[p.first] = d[nod] + p.second;
                if ( !inQueue[p.first])
                {
                    cntinQ[p.first]++;
                    if ( cntinQ[p.first] == n )
                    {
                        fout << "Ciclu negativ!";
                        exit(0);
                    }
                Q.push(p.first);
                inQueue[p.first] = 1;
				}
            }
        }
    }
 
    for ( int i = 2; i <= n; ++i )
        fout << d[i] << ' ';
}
 
void Read()
{
    fin >> n >> m;
    for ( int i = 1; i <= m; ++i )
    {
        fin >> x >> y >> z;
        G[x].push_back({y,z});
    }
}