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

using namespace std;

ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int INF = 1 << 30;
int N, M, D[50003], fr[50003];

typedef pair<int, int> muchie;
vector<muchie> G[50003];

int main()
{
    in >> N >> M;
    for(int i = 1; i <= M; ++ i)
    {
        int a, b, c;
        in >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }

    queue<int> Q;

    for(int i = 2; i <= N; ++ i)
        D[i] = INF;

    D[1] = D[0] = 0;
    Q.push(1);
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();

        for(vector < pair <int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++ it)
        {
            int cost = it->second, next = it->first;
            if(D[x] + cost < D[next])
            {
                D[next] = D[x] + cost;
                ++ fr[next];
                if(fr[next] > N)
                {
                    out << "Ciclu negativ!";
                    return 0;
                }
                Q.push(it->first);
            }
        }
    }

    for(int i = 2; i <= N; ++ i)
        out << (D[i] == INF ? 0 : D[i]) << ' ';
    out << '\n';
    return 0;
}