#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

using ll = long long;
const ll N = 410, inf = 1e16, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
    return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
    char ch = getc();  T fh = 0;   x = 0;
    while(ch < '0' || ch > '9')    fh |= (ch == '-'), ch = getc();
    while(ch >= '0' && ch <= '9')   x = x * 10 + ch - '0', ch = getc();
    x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args)   {read(x), read(args...);}
template<typename T>
void print(T x) {
    if(x < 0)  putchar('-'), x = -x;
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int n, m, g[N][N][3], u, v, op, w;
ll dis[N][N][3];
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    read(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) 
            for(int k : {0, 1, 2})  dis[i][j][k] = inf + inf;
    for(int i = 1; i <= m; ++i) {
        read(u, v, w, op);
        for(int j = 0; j <= op; ++j)    dis[u][v][j] = min(dis[u][v][j], (ll)w);
    }
    for(int i = 1; i <= n; ++i) dis[i][i][0] = dis[i][i][1] = dis[i][i][2] = 0;
    for(int u = 0; u <= 2; ++u)
        for(int k = 1; k <= n; ++k)
            for(int i = 1; i <= n; ++i) if(i != k)
                for(int j = 1; j <= n; ++j) if(k != j && i != j) {
                    dis[i][j][u] = min(dis[i][j][u], dis[i][k][u] + dis[k][j][u]);
                    if(u == 2)
                        dis[i][j][2] = min(dis[i][j][2], dis[i][j][1] + dis[j][i][0] + dis[i][j][1]);
                }
    for(int i = 1; i <= n; ++i, cout << "\n")
        for(int j = 1; j <= n; ++j) cout << (dis[i][j][2] < inf ? dis[i][j][2] : -1) << " ";
    return 0; 
}