#include <bits/stdc++.h>

#define i64 long long int

#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second

#define eb emplace_back

using namespace std;

inline int Read() {int res; return scanf("%d", &res), res; }
inline i64 Read64() {i64 res; return scanf("%lld", &res), res; }

const int INF_32 = 1e9;
const i64 INF_64 = 1e18;

const int N = 400 + 5; 

int n, m;
i64 t1[N][N], t2[N][N], t3[N][N];
priority_queue< pii > q;
int vis[N];
i64 dis[N], f[N][N];

void Dij(int st) {
	for(int i = 1; i <= n; ++ i) vis[i] = 0, dis[i] = INF_64;
	dis[st] = 0, q.push(mp(0, st));
	
	while(q.size()) {
		int u = q.top().se; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int v = 1; v <= n; ++ v) {
			if(vis[v]) continue;
			i64 w = t3[u][v];
			if(t2[u][v] < INF_64 && t1[v][u] < INF_64) w = min(w, t2[u][v] + t1[v][u] + t2[u][v]);
			if(w == INF_64) continue;
			if(dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				q.push(mp(-dis[v], v));
			}
		}
	}
}

int main() {
	n = Read(), m = Read();
	
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= n; ++ j) {
			if(i != j) t1[i][j] = INF_64, t2[i][j] = INF_64, t3[i][j] = INF_64;
		}
	}
	
	for(int i = 1; i <= m; ++ i) {
		int u = Read(), v = Read(), w = Read(), c = Read();
		if(c >= 0) t1[u][v] = min(t1[u][v], (i64)w);
		if(c >= 1) t2[u][v] = min(t2[u][v], (i64)w);
		if(c >= 2) t3[u][v] = min(t3[u][v], (i64)w); 
	}
	
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= n; ++ j) {
			for(int k = 1; k <= n; ++ k) {
				t1[j][k] = min(t1[j][k], t1[j][i] + t1[i][k]);
				t2[j][k] = min(t2[j][k], t2[j][i] + t2[i][k]);
				t3[j][k] = min(t3[j][k], t3[j][i] + t3[i][k]);
			}
		}
	}
	
	for(int i = 1; i <= n; ++ i) {
		Dij(i);
		for(int j = 1; j <= n; ++ j) f[i][j] = dis[j] == INF_64 ? -1 : dis[j];
	}
	
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= n; ++ j) printf("%lld ", f[i][j]);
		puts("");
	}
	
	return 0;
}