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

#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>

int N, M;
int D[2010];
vector<pii> V[2010];

int unit(int s)
{
    int ret = 1e18;
    memset(D, -1, sizeof(D));
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push({0, s});
    while(que.size())
    {
        pii tmp = que.top();
        que.pop();
        int v = tmp.second;
        int d = tmp.first;
        if(D[v] != -1)continue;
        D[v] = d;
        for(auto e : V[v])
        {
            int n = e.first;
            int c = e.second;
            if(n == s)ret = min(ret, d + c);
            else que.push({d + c, n});
        }
    }

    if(ret == 1e18)return -1;
    return ret;
}

signed main()
{
    cin >> N >> M;
    rep(i, M)
    {
        int a, b, c;
        cin >> a >> b >> c;
        V[a].push_back({b, c});
    }

    for(int i = 1; i <= N; i++)cout << unit(i) << endl;

    return 0;
}

//Inshallah , Boys played well..!!
 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pb push_back
#define pf push_front
#define mk make_pair
#define f(i,j,n) for(ll i=j;i<n;i++)
#define r(i,n,j) for(ll i=n-1;i>=j;i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define Test int t;cin>>t;while(t--)
#define mod 1000000007
#define md 998244353
#define MIN INT_MIN
#define MAX INT_MAX
#define inf LLONG_MAX
#define all(container) container.begin() , container.end()
#define rall(container) container.rbegin() , container.rend()
#define sz(container) (int)container.size()
#define vll vector<long long>
#define vi vector<int>
#define pii pair <int , int>
#define pll pair <ll , ll>
#define fi first
#define se second
#define setp(x) setprecision(x)
#define meme(x,i) memset(x,i,sizeof(x))
#define lb lower_bound
#define ub upper_bound
#define me max_element
#define debug(this) cout << "this = " << this << endl;
const int N = 2005;
vector<pair<int,int>> g[N];
int dis[N][N],dis2[N][N],w;
int n,m,x,y;
int z;
void dijikstra(int u){
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    pq.push({0,u});
    while(!pq.empty()){
        pair<int,int> p=pq.top();
        pq.pop();
        for(auto i:g[p.se]){
            if(dis2[u][i.fi]>dis2[u][p.se]+i.se){
                dis2[u][i.fi]=dis2[u][p.se]+i.se;
                pq.push({dis2[i.fi][u],i.fi});
            }
        }
    }
}
void solve() {
    cin >> n >> m;
    f(i,0,n+2){
        f(j,0,n+2)
            dis[i][j]=dis2[i][j]=3e8;
    }
    f(i,0,m){
        cin >> x >> y >> w;
        dis[x][y]=min(dis[x][y],w);
    }
    f(i,1,n+1){
    	f(j,1,n+1){
    		if(dis[i][j]!=3e8 and i!=j)
        	g[i].pb({j,dis[i][j]});
    	}
    }
    f(i,1,n+1){
    	dis2[i][i]=0;
    	dijikstra(i);
    }
    f(i,1,n+1){
    	int ans=dis[i][i];
    	f(j,1,n+1){
    		if(i!=j)
    		ans=min(ans,dis2[i][j]+dis2[j][i]);
    	}
    	if(ans>=3e8)
    		cout << -1 << endl;
    	else 
    		cout << ans << endl;
    }
}
 
int main() {
    fast;
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) {
        //cout << "Case #" << i << ": ";
        solve();
    }
}
