#include<fstream>
#include<vector>
#include<queue>
#define INF ((2<<29) - 1)
using namespace std;

int nrNoduri;
vector< pair<int, int> > grafCosturi[50008];

int dmin[50008];

void citire();
bool bellmanFord(int* dmin);
void afisareOK();
void afisareCycle();

int main() {
	citire();

	if (bellmanFord(dmin)){
        afisareOK();
	}
	else{
        afisareCycle();
	}
	return 0;
}

void citire() {
	ifstream fin("bellmanford.in");
	int nrMuchii, i, nod1, nod2, cost;
    fin >> nrNoduri >> nrMuchii;
	for (i = 0; i < nrMuchii; i++){
        fin >> nod1 >> nod2 >> cost;
        grafCosturi[nod1 - 1].push_back(make_pair(nod2 - 1, cost));
	}

	fin.close();
}

bool bellmanFord(int* dmin){
    queue<int> coada;
    int i;
    int el, next, cost;
    int aparitii[50008];
    for (i = 0; i < nrNoduri; i++){
        dmin[i] = INF;
        aparitii[i] = 0;
    }
    coada.push(0);
    dmin[0] = 0;
    aparitii[0] = 1;
    while(!coada.empty()){
        el = coada.front();
        coada.pop();
        for (i = 0; i < grafCosturi[el].size(); i++){
            next = grafCosturi[el][i].first;
            cost = grafCosturi[el][i].second;
            if (dmin[el] + cost < dmin[next]){
                dmin[next] = dmin[el] + cost;
                aparitii[next]++;
                coada.push(next);
                if (aparitii[next] == nrNoduri){
                    return false;
                }
            }
        }
    }
    return true;
}


void afisareCycle() {
	ofstream fout("bellmanford.out");
    fout << "Ciclu negativ!\n";
	fout.close();
}

void afisareOK(){
    ofstream fout("bellmanford.out");
    int i;
    fout << dmin[1];
    for (i = 2; i < nrNoduri; i++){
        fout << ' ' << dmin[i];
    }
    fout << '\n';
	fout.close();
}