#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int INF = 1e9;
vector<vector<pair<int, int>>> adj;
vector<int> dist, nr_vis;
vector<bool> vis;
queue<int> q;
int n, m;

bool BellmanFord()
{
    dist[1] = 0;
    q.push(1);
    ++nr_vis[1];

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        vis[node] = false;

        for(auto nbh : adj[node])
        {
            int nbh_node = nbh.first;
            int cost = nbh.second;
            if(dist[node] + cost < dist[nbh_node])
            {
                dist[nbh_node] = dist[node] + cost;

                if(!vis[nbh_node])
                {
                    q.push(nbh_node);
                    vis[nbh_node] = true;
                    nr_vis[nbh_node]++;
                    if(nr_vis[nbh_node] >= n)
                        return false;
                }
            }
        }
    }
    return true;
}


int main()
{
    in >> n >> m;

    adj.resize(n + 1);
    dist.resize(n + 1, INF);
    nr_vis.resize(n + 1, 0);
    vis.resize(n + 1, false);

    for(int i = 0; i < m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        adj[x].emplace_back(y, cost);
    }


    if(!BellmanFord())
        out << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; ++i)
            out << dist[i] << ' ';

    return 0;
}