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

template < typename T > struct ZkwHeapNode {
	T value;
	size_t mark;
	ZkwHeapNode() {
	} ZkwHeapNode(const T & _value): value(_value) {
	}
};

template < typename T, typename Comp > class ZkwHeap {

	private:
		typedef ZkwHeapNode < T > Node;
		typedef ZkwHeap < T, Comp > Heap;

		Comp cmp;
		Node *NodeList;
		size_t n;
		T init_value;

		void fix(size_t _pos) {
			if (cmp(NodeList[_pos << 1].value, NodeList[(_pos << 1) + 1].value))
				NodeList[_pos] = NodeList[(_pos << 1) + 1];
			else
				NodeList[_pos] = NodeList[_pos << 1];
		}

	public:

		ZkwHeap(const unsigned & _MaxN, const T & _init_value): init_value(_init_value) {
			n = 1 << (1 + (size_t) (log(_MaxN) / log(2.0)));
			NodeList = new Node[n << 1];
			for (size_t i = 1; i <= n + n - 1; i++)
				NodeList[i].value = init_value;
			for (size_t i = n; i <= n + n - 1; i++)
				NodeList[i].mark = i - n + 1;
		}

		~ZkwHeap() {
			delete[]NodeList;
		}

		T top() {
			return NodeList[1].value;
		}

		T top_pos() {
			return NodeList[1].mark;
		}

		void modify(unsigned _position, const T & _new_value) {
			int _pos = _position + n - 1;
			NodeList[_pos].value = _new_value;
			while (_pos)
				fix(_pos >>= 1);
		}

		T pop() {
			T return_value = NodeList[1].value;
			modify(NodeList[1].mark, init_value);
			return return_value;
		}
};

int n;
int dis[2010][2010];
vector<int>g[10010];
inline void dijkstra(int s) {
	ZkwHeap<pair<int, int>, greater<pair<int, int> > >h(10000, make_pair(0x3f3f3f3f, 0x3f3f3f3f));
	dis[s][s] = 0;
	h.modify(s, make_pair(0, s));
	for (int i = 2; i <= n; i++) {
		pair<int, int> k = h.top();
		h.pop();
		dis[s][k.second] = dis[k.second][s] = k.first;
		for (int p : g[k.second]) {
			if (dis[p] > dis[k.second] + dis[k.second][p]) {
				dis[s][p] = dis[p][s] = dis[k.second][s] + dis[k.second][p];
				h.modify(p, make_pair(dis[s][p], p) );
			}
		}
	}
}
int main() {
	int n,m;
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	for(int i = 0; i<m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(v);
		g[v].push_back(u);
		g[u][v]=g[v][u]=w;
	}
	for(int i = 1;i<=n;++i)dijkstra(i);
	for(int i = 1;i<=n;++i)
	for(int j = 1;j<=n;++j)
	cout<<dis[i][j]<<" \n"[j==n];
}