#include <fstream>
#include <vector>
using namespace std;

const int INF = 250000000;

struct Edge
{
    int rightEnd;
    int cost;
    Edge(int y, int c)
    {
        rightEnd = y;
        cost = c;
    }
};

bool BellmanFord(vector<Edge> adjList[], int dist[], int N);

int main()
{
    int N, M, i, x, y, c;
    ifstream f("bellmanford.in");
    f >> N >> M;
    vector<Edge> adjList[N + 1];

    for (i = 1; i <= M; i++)
    {
        f >> x >> y >> c;
        adjList[x].push_back(Edge(y, c));
    }
    f.close();

    int dist[N + 1];
    for (i = 1; i <= N; i++)
        dist[i] = INF;
    dist[1] = 0;

    ofstream g("bellmanford.out");
    if (!BellmanFord(adjList, dist, N))
        g << "Ciclu negativ!";
    else
        for (i = 2; i <= N; i++)
            g << dist[i] << " ";

    return 0;
}

bool BellmanFord(vector<Edge> adjList[], int dist[], int N)
{
    int k, i, j;
    for (k = 1; k < N; k++)
        for (i = 1; i <= N; i++)
            for (j = 0; j < adjList[i].size(); j++)
                if (dist[adjList[i][j].rightEnd] > dist[i] + adjList[i][j].cost)
                    dist[adjList[i][j].rightEnd] = dist[i] + adjList[i][j].cost;

     for (i = 1; i <= N; i++)
            for (j = 0; j < adjList[i].size(); j++)
                if (dist[adjList[i][j].rightEnd] > dist[i] + adjList[i][j].cost)
                    return false;
    return true;
}