#include <bits/stdc++.h>
using namespace std;

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

struct Edge
{
    int dest, cost;
};

vector <Edge> v[50005];

int dist[50005], entered[50005], N, M;

bool inq[50005];

queue <int> q;

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

    for(int i = 1; i <= M; i++)
    {
        int x, y, z;

        fin >> x >> y >> z;

        v[x].push_back({y, z});
    }

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

    q.push(1);
    inq[1] = true;

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

        entered[node]++;
        inq[node] = false;

        if(entered[node] >= N + 2)
        {
            fout << "Ciclu negativ!";
            return 0;
        }

        for(int i = 0; i < v[node].size(); i++)
        {
            int dest = v[node][i].dest;
            int cost = v[node][i].cost;

            if(dist[node] + cost < dist[dest])
            {
                dist[dest] = dist[node] + cost;

                if(inq[dest] == false)
                    q.push(dest);
            }
        }
    }

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

    return 0;
}