#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 505;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
ll A[3][N][N], ans[N][N];

int main()
{
	int n, m, i, j, k, t, a, b, c, d;
	memset(A, 0x3f, sizeof(A));
	memset(ans, 0x3f, sizeof(ans));
	scanf("%d%d", &n, &m);
	for(t = 0; t < 3; t++)
		for(i = 1; i <= n; i++)
			A[t][i][i] = 0;
	for(i = 1; i <= n; i++)
		ans[i][i] = 0;
	for(i = 1; i <= m; i++)
	{
		scanf("%d%d%d%d", &a, &b, &c, &d);
		for(t = 0; t <= d; t++)
			A[t][a][b] = min(A[t][a][b], (ll)c);
	}
	for(t = 0; t < 3; t++)
		for(k = 1; k <= n; k++)
			for(i = 1; i <= n; i++)
				for(j = 1; j <= n; j++)
					A[t][i][j] = min(A[t][i][j], A[t][i][k] + A[t][k][j]);
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			for(k = 1; k <= n; k++)
				if(A[2][i][k] != inf && A[1][k][j] != inf && A[0][j][k] != inf)
					ans[i][j] = min(ans[i][j], A[2][i][k] + 2 * A[1][k][j] + A[0][j][k]);
			if(ans[i][j] == inf)
				printf("-1 ");
			else
				printf("%lld ", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}