#include <iostream> 
#include <algorithm>
using namespace std; 

const int MAXN = 10 * 1000 + 10;
const int oo = 1000 * 1000 * 1000 + 10;

int n, m;
int dist[MAXN][MAXN];

void inputEdges();
void floydWarshall();
void output();

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		fill(dist[i], dist[i] + n, oo);
		dist[i][i] = 0;
	}
	inputEdges();
	floydWarshall();
	output();
}

void inputEdges() {
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		dist[u][v] = min(dist[u][v], w);
	}
}

void floydWarshall() {
	for (int k = 1; k <= n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

void output() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cout << "distance from vertex " << i + 1 << " to vertex " << j + 1 << " is " << dist[i][j] << '\n';
}