#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll a[405][405][4], b[405][405][4];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    memset(a, 0x3f, sizeof a);
    int inf = a[0][0][0];

    for (int i = 0; i < m; ++i)
    {
        int x, y, c, d;
        cin >> x >> y >> c >> d;
        a[x][y][d] = min(a[x][y][d], (ll)c);
    }
    for (int i = 1; i <= n; ++i) a[i][i][0] = a[i][i][1] = a[i][i][2] = 0;

    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) 
    {
        a[i][j][1] = min(a[i][j][1], a[i][j][2]);
        a[i][j][0] = min(a[i][j][0], a[i][j][1]);
    }
    
    for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        a[i][j][0] = min(a[i][j][0], a[i][k][0] + a[k][j][0]);

    for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        a[i][j][1] = min(a[i][j][1], a[i][k][1] + a[k][j][1]);

    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j][2] = min(a[i][j][2], a[i][j][1] * 2 + a[j][i][0]);
    
    for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
    {
        a[i][j][2] = min(a[i][j][2], a[i][k][2] + a[k][j][2]);
    }

    for (int i = 1; i <= n; ++i, cout << "\n") for (int j = 1; j <= n; ++j)
    {
        if (a[i][j][2] > (ll)(1e15)) cout << "-1 ";
        else cout << a[i][j][2] << " ";
    }
}

/*
0 500 726 751 746
-1 0 226 251 246
-1 -1 0 40 20
-1 -1 -1 0 -1
-1 -1 -1 131 0
*/