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

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 50000;
const int INF = 500000000;

struct Edge
{
    int to, cost;
};

int N, M;
vector < Edge > g[NMAX + 5];

int dist[NMAX + 5];

bool seen[NMAX + 5];
int impr[NMAX + 5];

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({y, c});
    }

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

    queue <int> q;

    q.push(1);
    dist[1] = 0;

    seen[1] = 1;
    impr[1] = 1;

    while(!q.empty())
    {
        int node = q.front();
        q.pop();

        seen[node] = 0;

        for(auto it : g[node])
            if(dist[it.to] > dist[node] + it.cost)
            {
                dist[it.to] = dist[node] + it.cost;

                if(seen[it.to] == 0)
                {
                    seen[it.to] = 1;
                    impr[it.to]++;

                    if(impr[it.to] > N)
                    {
                        fout << "Ciclu negativ!\n";
                        return 0;
                    }

                    q.push(it.to);
                }
            }
    }

    for(int i = 2; i <= N; i++)
        fout << dist[i] << ' ';

    return 0;
}