#include <fstream>
#include <queue>
#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)
{
    bool inQueue[N + 1];
    int countQueue[N + 1];
    queue<int> q;
    int i;

    for (i = 1; i <= N; i++)
    {
        inQueue[i] = false;
        countQueue[i] = 0;
    }
    q.push(1);
    inQueue[1] = true;
    countQueue[1] = 1;
    int x;

    while(!q.empty())
    {
        x = q.front(), q.pop();
        inQueue[x] = false;
        for (i = 0; i < adjList[x].size(); i++)
            if (dist[adjList[x][i].rightEnd] > dist[x] + adjList[x][i].cost)
            {
                dist[adjList[x][i].rightEnd] = dist[x] + adjList[x][i].cost;
                if (!inQueue[adjList[x][i].rightEnd])
                {
                    countQueue[adjList[x][i].rightEnd]++;
                    if (countQueue[adjList[x][i].rightEnd] > N)
                        return false;
                    q.push(adjList[x][i].rightEnd);
                    inQueue[adjList[x][i].rightEnd] = true;
                }
            }
    }

    return true;
}