#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1001
int arr[MAX][MAX];
int f[MAX][MAX];
int route[MAX];
void InputArray(int n);
int GetSubArrayMax(int n);
void OutputArray(int n);
int minimumTotal(int n);
void OutputRoute(int n);
void OutputOptimalRoute(int n, int min);
void OutputArray1(int n);
int main() {
int t, n, max;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
InputArray(n);
int min = minimumTotal(n);
cout << min << endl;
OutputOptimalRoute(n, min);
cout << endl;
}
}
void InputArray(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < i + 1; j++) {
cin >> arr[i][j];
}
}
}
void OutputArray(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < i + 1; j++) {
cout << f[i][j] << " ";
}
cout << endl;
}
}
int minimumTotal(int n) {
f[0][0] = arr[0][0];
for (int i = 1; i < n; i++) {
f[i][0] = f[i - 1][0] + arr[i][0];
for (int j = 1; j < i; j++) {
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
}
f[i][i] = f[i - 1][i - 1] + arr[i][i];
}
int min = 1001;
for (int j = 0; j < n; j++) {
if (f[n - 1][j] < min) min = f[n - 1][j];
}
return min;
}
void OutputRoute(int n) {
for (int i = 0; i < n; i++) {
if(i == 0)
cout << minimumTotal(i + 1) << " ";
else {
cout << minimumTotal(i + 1) - minimumTotal(i) << " ";
}
}
}
void OutputArray1(int n) {
for (int i = 0; i < n; i++) {
cout << route[i] << " ";
}
}
void OutputOptimalRoute(int n, int min) {
int rowMin = min;
int index = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i + 1; j++) {
if (f[i][j] == rowMin) {
route[index] = arr[i][j];
rowMin = rowMin - route[index];
index++;
}
}
}
for (int i = n - 1; i >= 0; i--) {
if(i == 0) cout << route[i];
else cout << route[i] << "-->";
}
}