#include <fstream>
#include <vector>

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 nod[MAXN];


void sterge(int k)
{
    for (int i = 0; i < a.size(); ++i)
        if ( a[i].s = k ) a.erase(a.begin() + i);
}

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;
    while (k)
    {
        k = 0;
        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;
            nod[ a[i].n ] = 1;
        }
        for (int i = 1; i <= N; ++i)
            if ( nod[i] == 0 ) sterge(i);
            else nod[i] = 0;
    }


    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;
}