#include <bits/stdc++.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 405;
const ll inf = 1e18;
ll f[N][N][3];
int n, m;
inline void up(ll &x, ll y){ x = x > y ? y : x; }
int main(){
    read(n), read(m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int p = 0; p < 3; p++) if(i != j) f[i][j][p] = inf;    
    for(int i = 1, a, b, c, d; i <= m; i++){
        read(a), read(b), read(c), read(d);
        for(int p = 0; p <= d; p++) up(f[a][b][p], c);
    }
    for(int p = 0; p <= 2; p++){
        if(p == 2){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    up(f[i][j][p], f[i][j][1] * 2 + f[j][i][0]);
        }
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    up(f[i][j][p], f[i][k][p] + f[k][j][p]);
    }
    for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= n; j++) 
            printf("%lld ", f[i][j][2] == inf ? -1 : f[i][j][2]);
    return 0;
}