#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int R=2e5 + 5;
const int N=1e5 + 3;
const int M = 2e3 + 3;
const int INF=0x3f3f3f3f;
struct edge{
	int v,w,next;
}e[R*2];
int dis[N],head[2*N],cnt=0;
int a[M][M];
struct node{
	int u,d;
	bool operator <(const node&rhs) const{
	  return d>rhs.d;
	}
};
inline void addedge(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int n,m,s;
inline void Dij(){
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0;
	priority_queue<node> Q;
	Q.push((node){s,0});
	while(!Q.empty()){
		node fr=Q.top();Q.pop();
		int u=fr.u,d=fr.d;
		if(d!=dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v,w=e[i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				Q.push((node){v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>n>>m; 	
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(!a[x][y]) a[x][y] = z;
		a[x][y] = min(a[x][y], z);
		addedge(x,y,z);
	}
	for(int i = 1; i <= n; ++i) {
		s = i;
		Dij(); int ans = -1;
		for(int j = 1; j <= n; ++j) if(dis[j] != INF && a[j][i]) {
			if(ans == -1) ans = dis[j] + a[j][i];
			ans = min(ans, dis[j] + a[j][i]);

		}
		cout << ans << endl;
	}
	return 0;
}
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (decltype(end) i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (decltype(end) i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (decltype(beg) i = beg; end <= i; i--)
#define REP(n)              for (decltype(n) repeat_index = 0; repeat_index < n; repeat_index++)

using namespace std;

template<typename T, size_t S>
T minval(const T(&vals)[S])
{
	T val = numeric_limits<T>::max();
	FOR_LT(i, 0, S) {
		val = min(val, vals[i]);
	}
	return val;
}

template<typename T, size_t S>
T maxval(const T(&vals)[S])
{
	T val = numeric_limits<T>::min();
	FOR_LT(i, 0, S) {
		val = max(val, vals[i]);
	}
	return val;
}

struct E {
	int i;
	int c;
};


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n, m; cin >> n >> m;
	vector<vector<E>> es(n + 1);
	REP(m) {
		int a, b, c; cin >> a >> b >> c;
		es[a].push_back({ b, c });
	}

	vector<int64_t> cs(n + 1);
	FOR_LE(i, 1, n) {
		FOR_LE(j, 1, n) {
			cs[j] = INT64_MAX;
		}

		using S = std::pair<int, int>;
		auto cmp = [](const S& lhs, const S& rhs) { return lhs.second > rhs.second; };
		priority_queue<S, vector<S>, decltype(cmp)> s(cmp);

		s.push({i, 0});
		cs[i] = 0;

		bool has_goal = false;
		while (!s.empty()) {
			S c = s.top();
			s.pop();
			if (c.first == i && c.second != 0) {
				cout << c.second << endl;
				has_goal = true;
				break;
			}
			if (cs[c.first] < c.second) continue;

			cs[c.first] = c.second;
			for (auto& e : es[c.first]) {
				//cout << e.i << " " << c.second + e.c << endl;
				s.push({ e.i, c.second + e.c });
			}
		}

		if (!has_goal) {
			cout << -1 << endl;
		}
	}

	return 0;
}