#include <bits/stdc++.h>
using namespace std ;
const long long inf = 1e18 ;
void solve()
{
    int n , m ;
    cin >> n >> m ;
    vector<array<int , 4>> edge(m) ;
    for(int i = 0 ; i < m ; i ++)  for(int j = 0 ; j < 4 ; j ++)  cin >> edge[i][j] ;
    vector<vector<long long>> ans(n , vector<long long>(n , inf)) ; 
    auto go = [&](int limit)
    {
        vector<vector<long long>> dis(n , vector<long long>(n , inf)) ;
        for(int i = 0 ; i < n ; i ++)  dis[i][i] = 0 ;
        for(auto [a , b , c , d] : edge)
        {
            if(d < limit)  continue ;
            a -= 1 , b -= 1 ;
            dis[a][b] = min(dis[a][b] , 1ll * c) ;
        }
        for(int k = 0 ; k < n ; k ++)
            for(int i = 0 ; i < n ; i ++)
                for(int j = 0 ; j < n ; j ++)
                    dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;
        return dis ;
    } ;
    vector<vector<long long>> two = go(2) ;
    vector<vector<long long>> one = go(1) ;
    vector<vector<long long>> zero = go(0) ;

    auto cal = [&](int i , int j)
    {
        long long mn = two[i][j] ;
        for(int k = 0 ; k < n ; k ++)
        {
            mn = min(mn , two[i][k] + one[k][j] + zero[j][k] + one[k][j]) ;
        }
        return mn ;
    } ;

    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j ++)
            if(i != j)
                ans[i][j] = cal(i , j) ;

    for(int i = 0 ; i < n ; i ++)  ans[i][i] = 0 ;
    auto change = [&](long long x)
    {
        if(x > 1e17)  return -1ll ;
        return x ;
    } ;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j ++)
            cout << change(ans[i][j]) << " \n"[j == n - 1] ;
}
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;

    int T = 1 ;
    while (T --)  solve() ;

    return 0 ;
}