#include <iostream>
#include <fstream>
#include <vector>
#define infinit (1<<28)

using namespace std;

struct varf{
    int vf, cost;
};

struct edge{
    int srs, dest, wght;
};

int v, e;
int x, y, w;
int dist[50005];
int pred[50005];
vector<varf> graf[50005];
vector<edge> edges;
int s=1;

void initializare()
{
    for(int i=1; i<=v; i++)
        dist[i] = infinit;
    dist[1] = 0;
}

bool bellman_ford()
{
    initializare();
    for(int i=1; i < v; i++)
    {
        for(auto& edg: edges)
        {
            int u = edg.srs;
            int v = edg.dest;
            int w = edg.wght;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pred[v] = u;
            }
        }
    }
    for(auto& edg: edges)
    {
        int u = edg.srs;
        int v = edg.dest;
        int w = edg.wght;
        if(dist[v] > dist[u] + w)
        {
            return false;
        }
    }
    return true;
}

int main() {

    ifstream f("bellmanford.in");
    freopen("bellmanford.out", "w", stdout);
    f>>v>>e;
    for(int i=1; i<=e; i++)
    {
        f>>x>>y>>w;
        edges.push_back({x, y, w});
    }

    if(bellman_ford() == false)
    {
        cout<<"Ciclu negativ!";
        return 0;
    }

    for(int i=2; i<=v; i++)
        cout<<dist[i]<<' ';

    return 0;
}