#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();

        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[it.second], 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;
}