#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 <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define ll long long
using namespace std;
using P = pair<int, int>;

struct E {
    int to, co;
    E(int to=0, int co=0):
    to(to), co(co) {}
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<E>> g(n);
    rep(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].emplace_back(b, c);
    }
    const int INF = 1001001001;
    rep(sv, n){
        vector<int> dist(n, INF);
        priority_queue<P, vector<P>, greater<P>> q;
        auto push = [&](int v, int d){
            if(dist[v] <= d) return;
            dist[v] = d;
            q.emplace(d, v);
        };
        for (auto&&  e: g[sv]) push(e.to, e.co);
        while(!q.empty()){
            int d = q.top().first;
            int v = q.top().second;
            q.pop();
            if(dist[v] != d) continue;
            for (auto&& e : g[v]){
                push(e.to, d+e.co);
            }
        }
        int ans = dist[sv];
        if (ans == INF) ans = -1;
        cout << ans << endl;
    }
}