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

const int inf = 2e9;
const int MAXN = 50005;

struct edge
{
    int s,n,w;
};

using std::vector;
std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");
int N,M;
vector<edge> a;
vector<int> dist;


int main()
{
    in >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        edge temp;
        in >> temp.s >> temp.n >> temp.w;
        a.push_back(temp);
    }

    dist.resize(N + 1,inf);
    dist[1] = 0;

    int k = 1,cnt = 0;
    while (k && cnt < N - 1)
    {
        k = 0;
        cnt++;
        for (int i = 0; i < a.size(); ++i)
            if ( dist[a[i].s] + a[i].w < dist[a[i].n] ) {
            dist[a[i].n] = dist[a[i].s] + a[i].w;
            ++k;
        }
        std::cout << k << " ";
    }


    for (int i = 0; i < a.size(); ++i)
    if ( dist[a[i].s] + a[i].w < dist[a[i].n] ) {
        out << "Ciclu negativ!"; return 0;
    }

    for (int i = 2; i <= N; ++i)
        out << dist[i] << " ";


    in.close();
    out.close();
    return 0;
}