#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const ll mod = 1e9+7;
int sum(int a, int b){return (a+b) % mod;}
int sub(int a, int b){return (a + mod - b) % mod;}
int mul(int a, int b){return (1ll * a * b) % mod;}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b&1)res = mul(res,a);
		b >>= 1;
		a = mul(a,a);
	}
	return res;
}

const ll oo = (ll)1e18;

void dijkstra(int src,vector<ll> &dist,vector<vii> &graph){
	priority_queue<ii,vector<ii>,greater<ii>> pq;
	pq.push({0,src});
	dist[src] = 0;
	while(pq.size()){
		ii act = pq.top(); pq.pop();
		ll d = act.fi;
		int u = act.se;
		if(d > dist[u])continue;
		for(auto &sig : graph[u]){
			int v = sig.fi;
			ll c = sig.se;
			if(dist[u]+c < dist[v]){
				dist[v] = dist[u]+c;
				pq.push({dist[v],v});
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N,M; cin >> N >> M;
	vector<pair<int,ii>> edges;
	forn(i,0,M){
		int u,v,c; cin >> u >> v >> c; u--; v--;
		edges.pb({c,{u,v}});
	}
	forn(i,0,N){
		vector<vii> graph(N+1);
		for(auto &act : edges){
			int c = act.fi;
			int u = act.se.fi;
			int v = act.se.se;
			graph[u].pb({v,c});
			if(v == i){
				graph[u].pb({N,c});
			}
		}
		vector<ll> dist(N+1,oo);
		dijkstra(i,dist,graph);
		if(dist[N] == oo){
			cout << "-1\n";
			continue;
		}
		cout << dist[N] << '\n';
	}
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pii pair<int,int> 
using namespace std;
const int N=2e5+5,mod=1e9+7,INF=1e15;
int t,n,m,u,v,dist[N];
vector<pii>V[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
string s;
 main(){
 	cin>>n>>m;
 	for(int i=1;i<=m;i++){
 		cin>>u>>v>>t;
 		V[u].push_back({v,t});
	 }
	 for(int i=1;i<=n;i++){
	 	q.push({0,i});
	 	for(int j=1;j<=n;j++)
	 	dist[j]=INF;
	 	while(q.size()){
	 		int d=q.top().f;
	 		int u=q.top().s; 
	 		q.pop();
	 		if(d>dist[u]) continue;
	 		for(int j=0;j<V[u].size();j++){
	 			if(dist[V[u][j].f]>d+V[u][j].s){
	 				dist[V[u][j].f]=d+V[u][j].s;
	 				q.push({dist[V[u][j].f],V[u][j].f});
				 }
			 }
		 }
	 	if(dist[i]==INF) cout<<-1<<endl;
	 	else cout<<dist[i]<<endl;
	 }
}
