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

using namespace std;

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

typedef pair<int, int> PII;

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

int N, M;
vector<PII> G[NMAX];

int d[NMAX];

int visits[NMAX];
bool In_Queue[NMAX];

queue<int> Q;

static inline void Add_Edge(int x, int y, int z)
{
    G[x].push_back({z, y});

    return;
}

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

    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int x = 0, y = 0, z = 0;
        f >> x >> y >> z;

        Add_Edge(x, y, z);
    }

    return;
}

static inline void Initialize()
{
    for (int i = 1; i <= N; ++i)
        d[i] = INF, visits[i] = 0, In_Queue[i] = 0;

    return;
}

static inline void Solve()
{
    Initialize();

    Q.push(1), d[1] = 0, ++visits[1], In_Queue[1] = 1;

    while (!Q.empty())
    {
        int Node = Q.front();
        Q.pop(), In_Queue[Node] = 0;

        if (visits[Node] >= N)
        {
            g << "Ciclu negativ!" << '\n';

            return;
        }

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

                if (!In_Queue[it.second])
                    Q.push(it.second), ++visits[Node], In_Queue[it.second] = 1;
            }
    }

    for (int i = 2; i <= N; ++i)
    {
        g << d[i];

        if (i != N)
            g << ' ';
    }

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}