class Knoten{
    String  name;
    boolean markiert;
    Knoten(String s){ name = s; }
    public String toString(){ return name;}
}

class Graph{

    static final private int U  = Integer.MAX_VALUE;
    
    Knoten [] knoten;
    int knotenZahl;
    
    int[][] distanzen =
       {{  U, 181,   U,   U,   U,  34, 224,   U,   U},
       	{181,   U, 104,  66,   U,   U,  88,   U, 136}, 
       	{  U, 104,   U, 106,  96,   U,   U,   U,  93},
       	{  U,  66, 106,   U,   U, 174,   U,  30,   U}, 
       	{  U,   U,  96,   U,   U,   U,   U, 104,   U}, 
       	{ 34,   U,   U, 174,   U,   U,   U,   U,   U}, 
       	{224,  88,   U,   U,   U,   U,   U,   U,   U}, 
       	{  U,   U,   U,  30, 104,   U,   U,   U,   U},
       	{  U, 136,  93,   U,   U,   U,   U,   U,   U} };
       		
    Graph(){
    	String [] sk = { "Bonn", "Frankfurt", "Fulda", "Gießen", "Kassel", 	
                       "Köln", "Mannheim",  "Marburg", "Würzburg" };
      knotenZahl = sk.length;
      knoten = new Knoten [knotenZahl];
      for (int i=0; i < knotenZahl; i++) knoten[i] = new Knoten(sk[i]);
      }
    
    void floyd(){
       int l = knotenZahl;
       for (int y=0; y < l; y++)
         for (int x=0; x < l; x++)
           if (distanzen[x][y] < U)
             for (int z=0; z < l; z++)
               if (distanzen[y][z] < U)
                 distanzen[x][z] = Math.min(distanzen[x][z], distanzen[x][y]+distanzen[y][z]);
       }	    		

     void showDistanzen(){
     	int l = knotenZahl;
       for (int x=0; x < l; x++){
         for (int y=0; y < l; y++) System.out.printf("%4d",distanzen[x][y]);
         System.out.println();       
         }
      }
    }


public class GraphT {

    public static void main(String ... args) {
     Graph g = new Graph();
     g.floyd();
     g.showDistanzen();

    }
}