// bellmanford
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define pb push_back
#define inf (1<<30)+100
#define NMax 100005

using namespace std;

ofstream g("bellmanford.out");

int n, m;
vector<int> V[NMax];
vector<int> C[NMax];
int dist[NMax];
bool viz[NMax];
queue<int> q;

void read() {
	ifstream f("bellmanford.in");
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a, b, c;
		f>>a>>b>>c;
		V[a].pb(b);
		C[a].pb(c);
	}
	f.close();
}

void print() {
    ifstream f("bellmanford.in");
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int x,y,c;
        f>>x>>y>>c;
        if (dist[x] + c < dist[y]) {
            g<<"Ciclu negativ!\n";
            return;
        }
    }
    for (int i=2;i<=n;i++)
        g<<dist[i]<<' ';
}


void solve() {

	for (int i=1;i<=n;i++)
		dist[i] = inf;
	dist[1] = 0;

	int step = 0;
	
	q.push(1);
	while (!q.empty() && step <= (long long)n*m) {
		int nod = q.front();
		viz[nod] = false;
		q.pop();
		step++;

		for (unsigned i=0;i<V[nod].size();i++) {
			int vecin = V[nod][i];
			if (dist[vecin] > dist[nod] + C[nod][i]) {
				dist[vecin] = dist[nod] + C[nod][i];
				if (!viz[vecin]) {
				q.push(vecin);
				viz[vecin] = true;
			}
			}
		}
	}
}

int main() {

	read();
	solve();
	print();

	g.close();
	return 0;
}