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

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int nmax = 50000;
struct elem
{
    int node,cost;
};
int dist[nmax + 1];
int viz[nmax + 1];
queue<elem>q;
vector<elem>g[nmax + 1];
int n;

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

    elem start;
    start.node = 1;
    start.cost = 0;
    dist[start.node] = 0;

    q.push(start);
    bool negative_cycle = false;
    while(!q.empty() && negative_cycle == false)
    {
        int curent = q.front().node;
        int costcurent = q.front().cost;
        viz[curent]++;
        q.pop();
        if(viz[curent] == n)
        {
            negative_cycle = true;
            out<<"Ciclu negativ!";
            break;
        }
        for(int i = 0; i < g[curent].size(); i++)
        {
            elem vecin = g[curent][i];
            int nodevecin = g[curent][i].node;
            int costvecin = g[curent][i].cost;
            if(dist[nodevecin] > dist[curent] + costvecin)
            {
                dist[nodevecin] = costcurent + costvecin;
                q.push(vecin);
            }
        }

    }
    if(negative_cycle == false)
        for(int i = 2; i <= n; i++)
            out<<dist[i]<<' ';
}
int main()
{
    int m;
    in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int x;
        elem y;
        in>>x>>y.node>>y.cost;

        g[x].push_back(y);
    }
    bellmanford();
    return 0;
}