#include <bits/stdc++.h>
#define lzm0107
using namespace std;
using LL = long long;
using AI2 = array<int, 2>;
using PII = pair<int, int>;
using ULL = unsigned long long;
const int N = 4e2 + 10;

int n, m;
LL f[3][N][N];

int main(){
	ios::sync_with_stdio(false);
	*cin.tie(nullptr) << fixed << setprecision(20);

	memset(f, 0x3f, sizeof(f));
	
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		f[0][i][i] = f[1][i][i] = f[2][i][i] = 0;
	}
	for(int a, b, c, d, i = 1; i <= m; i ++ ){
		cin >> a >> b >> c >> d;
		for(int j = d; j >= 0; j -- ) f[j][a][b] = min(f[j][a][b], (long long)c);
	}
	for(int i = 0; i < 3; i ++ ){
		for(int a = 1; a <= n; a ++ ){
			for(int b = 1; b <= n; b ++ ){
				for(int c = 1; c <= n; c ++ ){
					f[i][b][c] = min(f[i][b][c], f[i][b][a] + f[i][a][c]);
				}
			}
		}
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= n; j ++ ){
			LL res = 0x3f3f3f3f3f3f3f3f;
			for(int k = 1; k <= n; k ++ ){
				if(f[2][i][k] != 0x3f3f3f3f3f3f3f3f && f[1][k][j] != 0x3f3f3f3f3f3f3f3f && f[0][j][k] != 0x3f3f3f3f3f3f3f3f){
					res = min(res, f[2][i][k] + (f[1][k][j] << 1) + f[0][j][k]);
				}
			}
			cout << (res == 0x3f3f3f3f3f3f3f3f ? -1 : res) << ' ';
		}
		cout << '\n';
	}
	return 0;
}