#include <fstream>
#include <vector>
#define MAX 50005
#define INF 1 << 30

using namespace std;

struct data{
    int edge, weight;
} nd;

vector<data> v[MAX];

int nodes, edges, d[MAX];
bool negCycle(0);

void read();
void bell();
void write();

int main(){
    read();
    bell();
    write();
    return 0;
}

void read(){
    ifstream fin ("bellmanford.in");
    fin >> nodes >> edges;
    int x, y ,z;
    for (int i = 1; i <= edges; ++i){
        fin >> x >> y >> z;
        nd.edge = y, nd.weight = z;
        v[x].push_back(nd);
    }
    for (int i = 1; i <= nodes; ++i)
        d[i] = INF;

    fin.close();
}

void bell(){
    d[1] = 0;
    bool done;

    for (int ii = 1; ii < nodes; ++ii){
        done = 1;
        for (int i = 1; i <= nodes; ++i)
            for (unsigned int j = 0; j < v[i].size(); ++j)
                if (d[v[i][j].edge] > d[i] + v[i][j].weight)
                    d[v[i][j].edge] = d[i] + v[i][j].weight,
                    done = 0;
        if (done)
            break;
    }

    for (int i = 1; i <= nodes; ++i)
        for (unsigned int j = 0; j < v[i].size(); ++j)
            if (d[v[i][j].edge] > d[i] + v[i][j].weight){
                negCycle = 1;
                return;
            }
}

void write(){
    ofstream fout ("bellmanford.out");
    if (negCycle){
        fout << "Ciclu negativ!";
        fout.close();
        return;
    }
    for (int i = 2; i <= nodes; ++i)
        fout << d[i] << " ";
    fout.close();
}