#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int SIZE = 50005;
const int INF = 0x3f3f3f3f;

int n, m;

vector < pair <int, int> > adj[SIZE];

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        adj[x].push_back(make_pair(y, z));
    }
}

void BellmanFord(int startNode)
{
    vector <int> dist(SIZE, INF);
    dist[startNode] = 0;

    int ok = 1;
    for (int k = 1; k <= n && ok != 0; k++)
    {
        ok = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < adj[i].size(); j++)
            {
                int node = i;
                int neighbour = adj[i][j].first;
                int cost = adj[i][j].second;

                if (dist[node] + cost < dist[neighbour])
                {
                    dist[neighbour] = dist[node] + cost;
                    ok = neighbour;
                }
            }
        }
    }

    if (ok != 0)
    {
        g << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i <= n; i++)
        {
            g << dist[i] << " ";
        }
    }
}

int main()
{
    Read();
    BellmanFord(1);

    return 0;
}