#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define all(v) v.begin(),v.end()
#define mp make_pair
#define space ' '
#define INF (1LL<<60)
#define graph vector<vector<edge>>
template<class T>int chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
struct edge{int to;int cst;edge(int to,int cst):to(to),cst(cst){}};


void dijkstra()
{
	int n,m;cin>>n>>m;
	graph g(n*2);
	for(int i=0;i<m;i++){
		int a,b,cst;cin>>a>>b>>cst;a--;b--;
		g[a].push_back(edge(b,cst));
		g[a+n].push_back(edge(b,cst));
		g[a].push_back(edge(b+n,cst));
	}
	for(int s=0;s<n;s++){
		int t=s+n;
		//ここからdijkstra
		vector<int>dist(n*2,INF);dist[s]=0;
		vector<int>prev(n*2,-1);
		//pair(d[v],[v])が要素のプラキューを作る
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
		pq.push(mp(dist[s],s));
		//反復
		while(!pq.empty()){
			//v : 使用済みでない頂点の最小がd[v]になる
			//d : vに対するkey値
			int v=pq.top().second;
			int d=pq.top().first;
			pq.pop();

			if(d>dist[v])continue;
			
			for(auto e:g[v]){
				if(chmin(dist[e.to],dist[v]+e.cst)){
					prev[e.to]=v;
					pq.push(mp(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF) cout<<-1<<endl;
		else{cout<<dist[t]<<endl;}
	}
}
main(){
	dijkstra();
}
#include <bits/stdc++.h>
using namespace std;


/* エイリアス */
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp make_pair


/* 関数マクロ */
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n, m) for (ll i = n; i <= m; ++i)
#define rep3(i, n, m) for (ll i = n; i >= m; --i)
#define all(v) v.begin(), v.end()
#define si(v) int(v.size())
#define UNIQUE(v) sort(all(v)), v.erase(unique(all(v)),v.end())
#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; IN(__VA_ARGS__);


/* 定数 */
const ll mod = 1e9 + 7;
const ll infll = (1LL << 62) - 1;
const ll inf = (1LL << 30) - 1;


/* その他 */
template<class S, class T> inline bool chmax(S &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class S, class T> inline bool chmin(S &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

void IN() {}

template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
  cin >> head;
  IN(tail...);
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  LL(n);
  set<ll> div;

  rep2(i, 1, sqrt(n)) {
    if (n % i == 0) {
      div.em(i);
      div.em(n/i);
    }
  }

  for (auto e : div) cout << e << endl;
}
