#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;
static const LL INF = 1LL << 60;

struct Dijkstra {
	vector<vector<pair<long long, long long>>> edges;

	Dijkstra(long long size) : edges(size) { }

	void add_edges(std::vector<long long>& A, std::vector<long long>& B) {
		for (int i = 0; i < A.size(); ++i) {
			add_edge(A[i], B[i]);
		}
	}

	void add_edges(std::vector<long long>& A, std::vector<long long>& B, std::vector<long long>& C) {
		for (int i = 0; i < A.size(); ++i) {
			add_edge(A[i], B[i], C[i]);
		}
	}

	void add_edge(long long a, long long b, long long c = 1) {
		edges[a].push_back({ b, c });
	}

	vector<long long> get_min_costs(long long start) {
		vector<long long> min_costs(edges.size(), 1LL << 60);
		priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<>> q;
		q.emplace(make_pair(0, start));
		while (!q.empty()) {
			pair<long long, long long> top = q.top();
			q.pop();
			long long cost = top.first, node = top.second;
			if (cost > min_costs[node]) continue;
			for (auto kv : edges[top.second]) {
				long long next_node = kv.first;
				long long next_cost = top.first + kv.second;
				if (next_cost < min_costs[next_node]) {
					min_costs[next_node] = next_cost;
					q.emplace(make_pair(next_cost, next_node));
				}
			}
		}
		return min_costs;
	}
};

void solve(long long N, long long M, std::vector<long long>& A, std::vector<long long>& B, std::vector<long long>& C) {
	Dijkstra dijkstra(N);
	dijkstra.add_edges(A, B, C);
	for (int i = 0; i < N; i++) {
		vector<LL> costs = dijkstra.get_min_costs(i);
		LL ans = costs[i];
		cout << (ans < INF ? ans : -1) << endl;
	}
}

int main() {
	long long N, M;
	std::cin >> N >> M;
	std::vector<long long> A(M), B(M), C(M);
	for (int i = 0; i < M; i++) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i];
		--B[i];
	}
	solve(N, M, A, B, C);
	return 0;
}



//================code===================//

#define TLE

#ifdef TLE
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>


#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long
#define fa(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>b;--i)
#define setp pair<pair<int,int>,int>
#define setl pair<LL,LL>
#define M_PI 3.14159265358979323846
#define micro 0.000001


using namespace std;

#ifdef OHSOLUTION
#define ce(t) cerr<<t
#define AT cerr << "\n=================ANS=================\n"
#define AE cerr << "\n=====================================\n"
#else
#define AT
#define AE
#define ce(t)
#define __popcnt __builtin_popcount
#endif

LL gcd(LL a, LL b) { return a % b ? gcd(b, a % b) : b; }
LL lcm(LL a, LL b) { return (a * b) / gcd(a, b); }

pair <int, int> vu[9] = { {0,1},{0,-1},{1,0} ,{-1,0},{0,0},{1,1}, {-1,1} , {1,-1},{-1,-1} }; //RDLU EWSN

template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl a, setl b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl a, setl b) { return a.second > b.second; } };

const int max_v = 2e3 + 7;
const int INF = 1e8 + 7;
const LL LNF = 1e18 + 7;
const LL mod = 1e9+7;

int v, e;
priority_queue<setl, vector<setl>, lcmp> pq;
vector<setl> adj[max_v];
int dist[max_v];
bool vist[max_v];

int dijk(int sp)
{
	while (!pq.empty()) pq.pop();

	fill(dist, dist + v, INF);
	memset(vist, 0, sizeof(vist));
	pq.push({ sp,0 });
	dist[sp] = 0;
	int ret = INF;

	while (!pq.empty())
	{
		setl cur;
		do
		{
			cur = pq.top(); pq.pop();
		} while (!pq.empty() && vist[cur.first]);

		if (vist[cur.first]) break;

		vist[cur.first] = 1;

		for (auto x : adj[cur.first])
		{
			if (dist[x.first] > dist[cur.first] + x.second)
			{
				dist[x.first] = dist[cur.first] + x.second;
				pq.push({ x.first,dist[x.first] });
			}

			if (x.first == sp)
			{
				ckmin(ret, dist[cur.first] + x.second);
			}
		}
	}

	return ret == INF ? -1 : ret;
}

int main()
{
#ifdef OHSOLUTION
	freopen("input.txt", "r", stdin);
#endif	
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ci(v >> e);
	fa(i, 0, e)
	{
		int x, y, cost; ci(x >> y >> cost); --x, --y;
		adj[x].push_back({ y,cost });
	}

	fa(i, 0, v) co(dijk(i) << "\n");
	return 0;
}