#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(ff, aa) for(auto ff : aa)
#define rep2(ff, aa) for(auto &ff : aa)
#define ALL(a)  (a).begin(),(a).end()
using pii = pair<int, int>;
using Graph = vector<vector<ll>>;

void daiku(const vector<ll> &kyori,const vector<vector<pii>> &gg,const ll ss,vector<ll> &dis){

ll nn=gg.size();
vector<ll> rr(nn,INF);
dis=rr;
priority_queue<pii,vector<pii>,greater<pii>> pq;
dis[ss]=0;
pq.emplace(dis[ss],ss);

while(!pq.empty()){
auto ww=pq.top();
pq.pop();
ll genzai=ww.second;
if(ww.first>dis[genzai]) continue;
for(auto &ee:gg[genzai]){
if(chmin(dis[ee.first],dis[genzai]+kyori[ee.second])){
pq.emplace(dis[ee.first],ee.first);
}
}

}

}

int main(){

ll nn,mm,start;
cin>>nn>>mm;

vector<vector<pii>> gg(nn);
vector<ll> kyori(mm);
vector<ll> ans(nn,INF);
vector<vector<pii>> wwee(nn);

ll ss,tt,dd;
rep(i,mm){
cin>>ss>>tt>>dd;
ss--;
tt--;
gg[ss].push_back({tt,i});
wwee[tt].push_back({ss,i});
kyori[i]=dd;
}

ll aaee=INF;
rep(i,nn){
aaee=INF;
daiku(kyori,gg,i,ans);
for(auto ee : wwee[i]){
chmin(aaee,(ans[ee.first]+kyori[ee.second]));
}
if(aaee>=INF){
cout<<-1<<endl;
}else{
cout<<aaee<<endl;
}
}

}
 /*
    Stay motivated and keep working hard
*/
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define int long long 
#define pb push_back
#define cntbit __builtin_popcount
#define fr first
#define mem(arr, val) memset(arr, val, sizeof(arr))
#define sc second
#define sz(v) ((int)(v).size())
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,p) for(int i=a-1;i>=p;i--) 
#define md 998244353
#define vi vector<int>
#define vp vector<pair<int,int> >
#define ml map<int,int>
#define MPI 3.1415926536
#define in insert
#define endl "\n"
#define ub  upper_bound
#define lb  lower_bound
#define gcd __gcd
#define setval(a,b) memset(a,b,sizeof(a))
#define lwr lower_bound
#define pii pair<int,int>
#define upr upper_bound
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//CANDIDATE MASTER TOH BNKE RHUNGA
//dsu is pel concept
//KMP is pel concept 
int k,n,t,i,j=0,m;
const int N=2e3+5;
int md2;
inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
 
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}
 
inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}
 
inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
 
inline int inv(int a) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  if (u < 0) u += md;
  return u;
}
vp graph[N];
const int inf=1e9;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		graph[a].pb({b,c});
	} 
	for(int i=1;i<=n;i++)
	{
		priority_queue <pii,vp,greater<pii>> pq;
		pq.push({0,i});
		vector <int> dist(n+1,inf); 
		while(pq.size())
		{
	    pii p=pq.top();
	    pq.pop();
	    for(auto it:graph[p.sc])
	    {
	    	if(dist[it.fr]>p.fr+it.sc)
	    	{	
	    	dist[it.fr]=p.fr+it.sc;
			pq.push({dist[it.fr],it.fr});	
			}
		}
		}
	    if(dist[i]==inf)
	    cout<<-1;
	    else
	    cout<<dist[i];
		cout<<endl;
	}
}
