class Algo {
    static int size = 7;
    static int maxint = Integer.MAX_VALUE;
    public static int[] t = {1,9,9,2,1,1,0};

    public static int[][] delta = new int[size][size];
    public static int[][] poids = new int[size][size];

    public static void poids(){
	for(int i = 0; i < size; i++)
	    for(int j = 0; j < size; j++)
		delta[i][j] = maxint;

	for(int i = 0; i < size; i++)
	    for(int j = i; j < size; j++)
		for(int k = i; k < j; k++)
		    poids [i][j] += t[k];

    }

    public static int min(int i, int j){
	int n = maxint;
	for(int k = i; k < j; k++)
	    n = Math.min (poids[i][k] + poids[k+1][j] + desequilibre(i,k) + desequilibre(k+1, j), n);
	return n;
    }

    public static int desequilibre(int i, int j){
	if (delta[i][j] != maxint)
	    return delta[i][j];
	else
	    if (i>j)
		return maxint;
	    else if (i == j)
		return (delta[i][j] = 0);
	    else
		return (delta[i][j] = min(i,j));
    }

    public static String complete(int i){
	String s = i + " ";
	if(i<10)
	    s = " " + s;
	return s;
    }

    public static void affiche(int[][] t){
	for(int i = 0; i < size; i++){
	    for(int j = 0; j < size; j++){
		if(i>j)
		    System.out.print("__ ");
		else
		    System.out.print(complete(t[i][j]));
	    }
	    System.out.println("");
	}
    }

    public static void main (String[] args){
	poids();
	desequilibre(0,size-1);
	affiche(delta);
    }
}