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

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;

struct elem
{
    int node,cost;
};
vector<elem>g[50001];
queue<elem>q;

int dist[50001];
int viz[50001];

void bellmanford()
{
    memset(dist, 0x3f3f3f, sizeof dist);

    int negative_cycle = false;

    elem start;
    start.node = 1;
    start.cost = 0;

    q.push(start);
    dist[start.node] = 0;

    while(!q.empty() && negative_cycle == false)
    {
        int curent_node = q.front().node;
        int curent_cost = q.front().cost;
        q.pop();
        viz[curent_node]++;
        if(viz[curent_node] == n)
        {
            negative_cycle = true;
            out<< "Ciclu negativ!";
            break;
        }
        for(int i = 0; i < g[curent_node].size(); i++)
        {
            elem vecin = g[curent_node][i];
            int vecin_node = g[curent_node][i].node;
            int vecin_cost = g[curent_node][i].cost;
            if(dist[vecin_node] > dist[curent_node] + vecin_cost)
            {
                q.push(vecin);
                dist[vecin_node] = dist[curent_node] + vecin_cost;
            }
        }
    }
    if(negative_cycle == false)
        for(int i = 2; i <= n; i++)
            out<<dist[i]<<' ';

}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m ; i++)
    {
        elem x,y;
        in>>x.node>>y.node>>y.cost;
        g[x.node].push_back(y);
    }
    bellmanford();
    return 0;
}