#include <bits/stdc++.h>
#define MAXN 50001
#define infinity (1<<30)
using namespace std;

struct Node {
    int node;
    int cost;
};

vector<Node> graph[MAXN];
int M, N;

int dist[MAXN];
bool inQueue[MAXN];
int cnt[MAXN];

int heap[MAXN + 10];
int heap_size = 0;

void heap_push(int node)
{
    heap_size ++;
    heap[heap_size] = node;

    int i = heap_size;
    while(i > 1 && dist[heap[i >> 1]] > dist[heap[i]]) heap[i] ^= (heap[i >> 1] ^= (heap[i] ^= heap[i >> 1]));
}

void heap_pop(void)
{
    heap[1] ^= (heap[heap_size] ^= (heap[1] ^= heap[heap_size]));

    heap_size--;

    int i = 1;
    int j = (i << 1);

    while(j <= heap_size )
    {
        if((j + 1 <= heap_size)&& (dist[heap[j]] > dist[heap[j + 1]])) j++;

        if(dist[heap[j]] < dist[heap[i]])
        {
            heap[i] ^= (heap[j] ^= (heap[i] ^= heap[j]));
            i = j;
            j = (i << 1);
        }
        else return;
    }
}

void read_from_file()
{
    ifstream fin("bellmanford.in");
    fin >> N >> M;

    int x, y, c;

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


void dijkstra()
{
    ofstream fout("bellmanford.out");

    for(int i = 1; i <= N; ++i) dist[i] = infinity, cnt[i] = 0;

    dist[1] = 0;
    heap_push(1);

    while(heap_size > 0)
    {
        int node = heap[1];
        heap_pop();
        inQueue[node] = false;

        for(vector<Node>::iterator i = graph[node].begin(); i != graph[node].end(); ++i)
        {
            if(i->cost + dist[node] < dist[i->node])
            {
                dist[i->node] = dist[node] + i->cost;

                if(inQueue[i->node] == false)
                {
                    ++cnt[i->node];

                    if(cnt[i->node] > N)
                    {
                        fout << "Ciclu negativ!";
                        return;
                    }
                    inQueue[i->node] = true;
                    heap_push(i->node);
                }
            }
        }
    }

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

int main()
{
    ios_base::sync_with_stdio(false);

    read_from_file();

    dijkstra();

}