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

using namespace std;

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

typedef pair < int, int > PII;

const int NMAX = 5e4 + 5, INF = 1e9;

int N, M, X, Y, C, cnt[NMAX];

vector < PII > G[NMAX];

bool Sel[NMAX];

queue < int > Q;

int D[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X >> Y >> C;

        G[X].push_back({C, Y});
    }

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
        Sel[i] = 0, D[i] = INF;

    D[1] = 0;
    Sel[1] = 1;
    cnt[1] = 1;

    Q.push(1);

    while(!Q.empty())
    {
        int Node = Q.front();
        Q.pop();

        Sel[Node] = 0;

        for(auto it : G[Node])
            if(D[Node] + it.first < D[it.second])
            {
                D[it.second] = D[Node] + it.first;

                if(Sel[it.second])
                    continue;

                if(++cnt[it.second] > N)
                {
                    g << "Ciclu negativ!" << '\n';

                    return;
                }

                Sel[it.second] = 1;

                Q.push(it.second);
            }
    }

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

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}