#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");
constexpr int nmax = 50001;
int n, m;

const long long inf  = 1e17;
long long c[nmax];
int qv[nmax];
bool inq[nmax];
std::vector<std::pair<int, int>> adj[nmax];

bool bf(int s)
{
    inq[s] = true;
    for ( int i = 1; i <= n; ++i )
       c[i] = inf;
    c[s] = 0;
    std::queue<int> q;
    q.push(s);
        while ( !q.empty() )
        {
            std::cout << "DEBUG " << std::endl;
            int u = q.front();
            qv[u]++;
            q.pop();
            if ( qv[u] > n )
               return false;
            inq[u] = false;
            for ( auto id : adj[u] )
            {
                int v = id.first;
                if ( c[v] < c[u] + id.second )
                   continue;
                c[v] = c[u] + id.second;
                if ( !inq[v] )
                  q.push(v), inq[v] = true;
            }
        }
        return true;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    in.tie(0);
    in >> n >> m;

    for ( int i = 1; i <= m; ++i )
    {
        int a, b, c;
        in >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    if ( !bf(1) )
      out << "Ciclu negativ!";
    else
    {
        for ( int i = 2; i <= n; ++i )
           out << c[i] << " ";
    }
    return 0;
}