#include <bits/stdc++.h>

#define i64 long long

using namespace std;

const i64 N = 410;

i64 n, m, a, b, c, d;
i64 Mp[N][N][3];

int main() {
	scanf("%lld%lld", &n, &m);
	for (i64 i = 1; i <= n; i ++) {
		for (i64 j = 1; j <= n; j ++) {
			for (i64 k = 0; k <= 2; k ++) {
				Mp[i][j][k] = 1e18;
			}
		}
	}
	
	for (i64 i = 1; i <= m; i ++) {
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		for (i64 j = d; j >= 0; j --) Mp[a][b][j] = min(Mp[a][b][j], c);
	}
	for (i64 i = 1; i <= n; i ++) Mp[i][i][0] = Mp[i][i][1] = Mp[i][i][2] = 0;
	
	for (i64 k = 1; k <= n; k ++) {
		for (i64 i = 1; i <= n; i ++) {
			for (i64 j = 1; j <= n; j ++) {
				Mp[i][j][0] = min(Mp[i][j][0], Mp[i][k][0] + Mp[k][j][0]);
			}
		}
	}
	
	for (i64 k = 1; k <= n; k ++) {
		for (i64 i = 1; i <= n; i ++) {
			for (i64 j = 1; j <= n; j ++) {
				Mp[i][j][1] = min(Mp[i][j][1], Mp[i][k][1] + Mp[k][j][1]);
			}
		}
	}
	
	for (i64 k = 1; k <= n; k ++) {
		for (i64 i = 1; i <= n; i ++) {
			for (i64 j = 1; j <= n; j ++) {
				Mp[i][j][2] = min(Mp[i][j][2], Mp[i][k][2] + Mp[k][j][2]);
				Mp[i][j][2] = min(Mp[i][j][2], Mp[i][k][2] + Mp[k][j][1] * 2 + Mp[j][k][0]);
			}
		}
	}
	
	for (i64 i = 1; i <= n; i ++) {
		for (i64 j = 1; j <= n; j ++) {
			if (Mp[i][j][2] >= 1e18) Mp[i][j][2] = -1;
			printf("%lld ", Mp[i][j][2]);
		}
		puts("");
	}
	
	return 0;
}