#include <iostream>
#include <vector>
#include <fstream>
#include <tuple>
#include <string.h>
#include <queue>

using namespace std;

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

#define INF 10000000

int nodes, edge_nr;
vector< vector <pair<int, int> > > graph;
int dist[100000];

void bellman_ford(int node)
{
    bool inQueue[nodes + 1] = { false };
    for (int i = 0; i <= nodes; i++)
    {
        dist[i] = INF;
    }
    dist[node] = 0;
 
    queue<int> q;
    q.push(node);
    inQueue[node] = true;
 
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        for (int i = 0; i < graph[u].size(); i++) {
 
            int v = graph[u][i].first;
            int weight = graph[u][i].second;
 
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
 
    bool changes = false;

    if(changes)
        fout << "Ciclu negativ!";
    else
    {
        for(int i = 2; i <= nodes; i++)
        {
            fout << dist[i] << ' ';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b, w;
    fin >> nodes >> edge_nr;
    graph = vector< vector <pair<int,int> > > (nodes+1);
    for(int i = 0; i < edge_nr; i++)
    {
        fin >> a >> b >> w;
        graph[a].push_back({b, w});
    }
    bellman_ford(1);

    return 0;
}