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

using namespace std;

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

typedef pair < int, int > Edge;

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

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

int d[NMAX];
bool Sel[NMAX];
int cnts[NMAX];

queue < int > Q;

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

    f >> N >> M;

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

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

    return;
}

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

    d[1] = 0, Sel[1] = 1, ++cnts[1], Q.push(1);

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

        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;
                else
                {
                    ++cnts[it.second];

                    if(cnts[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];

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

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}