floyd-warshall

#define __USE_CIN
//   __USE_CIN or __USE_SCANF
//   desynchronized <iostream> is faster than <cstdio> !!!
using namespace std;

#include <vector>
#include <set>
#include <queue>
#include <map>

#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>

#ifdef __USE_CIN
#include <iostream>
#define INT(x) int x; cin>>x
#define LL(x) long long x; cin>>x
#define ULL(x) unsigned long long x; cin>>x
#define STR(s) string (s); cin>>(s);
#define nl cout << '\n';

#elif defined __USE_SCANF
#include <cstdio>
#define INT(x) int x; scanf("%d", &x)
#define LL(x) long long x; scanf("%lld", &x)
#define ULL(x) unsigned long long x; scanf("%llu", &x)
#define STR(s, i) char *(s) = new char[(i)+1]; scanf("%s", (s));
#define nl printf("\n");
#elif !defined __USE_CIN && !defined __USE_SCANF
#error Standard input flag not set.
#endif

#define ll long long
#define ull unsigned long long
#define ui unsigned int

typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair< pair<int, int>, pair<int, int> > ppi;
typedef vector< int > vi;
typedef vector<bool > vb;
typedef vector< long long > vll;
typedef vector< pi > vpi;
typedef vector<vector<int> > vvi;
typedef vector< vector<long long> > vvll;
typedef vector<vector< pi > > vvpi;

const int INT_INF = 2147483647;
const ll LL_INF = 9223372036854775807;

#define fr(x,y) for(int (x)=0; (x)<(y); (x)++)
#define fr1(x,y) for(int (x)=1; (x)<=(y); (x)++)
#define rf(x,y) for(int (x)=(y); (x)>=0; (x)--)
#define frl(x,y) for(ll (x)=0; (x)<(y); (x)++)
#define zajmodulo(x,y) ((x)%(y)+(y))%(y)
#define matrixINT(NAME,X,Y,VAR) vvi (NAME)((X), vi((Y), (VAR)))
#define matrixLL(NAME,X,Y,VAR) vvll (NAME)((X), vl((Y), (VAR)))

pll EGCD(ll a, ll b) { if (b == 0) return pll(1, 0);    pll xy = EGCD(b, a%b);  return pll(xy.second, xy.first - (a / b)*xy.second); }
//returni a(mod p) ale trzeba użyć zajmodulo(ECGD.f, ECGD.s)
/*
    .........................................
    #########################################
        _______              _
       |__   __|            | |
          | | ___   ___  ___| |_ ___ _ __
          | |/ _ \ / _ \/ __| __/ _ \ '__|
          | | (_) | (_) \__ \ ||  __/ |
          |_|\___/ \___/|___/\__\___|_|

    #########################################
    .........................................
*/

/*
   --------
    Floyd-Warshall for calculating shortest paths between each pair of nodes in an undirected graph;
    input:
    T - test cases
    n m - nodes, edges
    a b c - edge a-b and b-a with weight c
    output:
    matrix n x n with shortest paths - dist[i][j] = -1 if path i-j does not exists
   --------
*/
int n, m;
vvll dist;
const ll MX = 5000000000;

void pie(){
    cin >> n >> m;
    dist.resize(0);
    dist.resize(n);
    fr(i, n) {
        dist[i].resize(n-i, MX);
        dist[i][0] = 0;
    }

    int a, b;
    ll c;
    fr(i, m) {
        cin >> a >> b >> c; --a; --b;
        dist[min(a, b)][max(a,b)-min(a,b)] = c;
    }
    fr(u, n){
        fr(v1, n){ // v1 <= v2
            for(int v2 = v1; v2 < n; v2++)
                if(dist[v1][v2-v1] > dist[min(v1, u)][max(v1, u) - min(v1, u)] +  dist[min(v2, u)][max(v2, u) - min(v2, u)])
                    dist[v1][v2-v1] = dist[min(v1, u)][max(v1, u) - min(v1, u)] +  dist[min(v2, u)][max(v2, u) - min(v2, u)];
        }
    }

    fr(i, n) {
        fr(j, n){
            if (dist[min(i, j)][max(i, j) - min(i, j)] == MX) cout << "-1 ";
            else cout << dist[min(i, j)][max(i, j) - min(i, j)] << " ";
        }
        nl;
    }

    return;
}
/*
*
*
*
*
*
*
*
*/
int main() {
#ifdef __USE_CIN
    ios_base::sync_with_stdio(false);
#endif
    INT(T);
    while(T--) pie();
    return 0;
}