#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int n,m;
int d[1000][1000];

int main() {
	freopen("test.in","r",stdin);
	scanf("%d %d",&n,&m);
	// init
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) d[i][j]=1e9;
	}
	for (int i=1;i<=n;i++) d[i][i]=0;
	// input
	for (int i=0;i<m;i++) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		d[a][b]=c;
		d[b][a]=c;
	}
	// floyd-warshall
	for (int k=1;k<=n;k++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}
	// output
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			printf("%d %d: %d\n",i,j,d[i][j]);
		}
	}
	return 0;
}