#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int solve(vector<vector<ii>>& a, int s) {
  int n = SZ(a);
  priority_queue<ii, vector<ii>, greater<ii>> Q;
  vector<int> d(n, inf<int>);
  d[s] = 0;
  Q.push({d[s], s});
  bool first = true;
  while (!Q.empty()) {
    auto [dd, u] = Q.top();
    Q.pop();
    if (dd != d[u]) continue;
    // trace(dd, u);
    if (u == s) {
      if (first) {
        first = false;
        d[u] = inf<int>;
      } else {
        return dd;
      }
    }
    for (auto& [v, w] : a[u]) {
      if (d[v] > dd + w) {
        d[v] = dd + w;
        Q.push({d[v], v});
      }
    }
  }
  return -1;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<ii>> a(n);
  for (int i = 0; i < m; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    a[x].push_back({y, z});
  }
  for (int i = 0; i < n; ++i) {
    int ret = solve(a, i);
    cout << ret << '\n';
  }
  return 0;
}

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
int n,m,e[2005][2005],Dis[2005][2005],vis[2005],dis[2005];
vector <pii > g[2005]; 
const int inf=0x3f3f3f3f;
void dij(int x)
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[x]=0;
	priority_queue <pii > q;
	q.push(mp(0,x)); 
	while(!q.empty())
	{
		int u=q.top().se;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].fi;
			if(vis[v]) continue;
			if(dis[u]+g[u][i].se<dis[v])
			{
				dis[v]=dis[u]+g[u][i].se;
				q.push(mp(-dis[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++) if(i!=x) Dis[x][i]=dis[i];
}
int solve(int x)
{
	int ans=inf;
	for(int i=1;i<=n;i++)
	{
		if(x==i)
		{
			ans=min(ans,Dis[x][x]);
			continue;
		}
		int dist=Dis[x][i]+Dis[i][x];
		ans=min(ans,dist);
	}
	if(ans>=inf) return -1;
	else return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=Dis[i][j]=inf;
	while(m--)
	{
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		if(a==b) Dis[a][b]=min(Dis[a][b],w);
		else e[a][b]=min(e[a][b],w);
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
	{
		if(i==j) continue;
		if(e[i][j]!=inf) g[i].push_back(mp(j,e[i][j]));
	}
	for(int i=1;i<=n;i++) dij(i);
	for(int i=1;i<=n;i++) cout<<solve(i)<<endl;
	return 0;
}