import java.util.Scanner;
class GraphMatrix2
{
    static final int MaxNum=20;
    char[] Vertex=new char[MaxNum];
    int GType;
    int VertexNum;
    int EdgeNum;
    int[][] EdgeWeight=new int [MaxNum][MaxNum];
    int[] isTrav=new int[MaxNum];
}
public class ShortestPath {
    
        static final int MaxValue=67777;
        static int[] path=new int [GraphMatrix2.MaxNum];
        static int[] tmpvertex=new int [GraphMatrix2.MaxNum];
        static Scanner input= new Scanner(System.in);
        static void CreateGraph(GraphMatrix2 GM)
        {
            int i,j,k;
            int weight;
            char EstartV,EendV; //  start and end vertex of of edge;
            
            System.out.println("enter the info. of graph");
            for(i=0;i<GM.VertexNum;i++)  //enter the vertex
            {
                System.out.printf("the %d vertex", i+1);
                GM.Vertex[i]=(input.next().toCharArray())[0]; //save in array
            }
            System.out.println("enter the edge and the weight");
            for(k=0;k<GM.EdgeNum;k++)
            {
                System.out.printf("the %d edge", k+1);
                EstartV=input.next().charAt(0);
                EendV=input.next().charAt(0);   
                weight=input.nextInt();
                for(i=0;EstartV!=GM.Vertex[i];i++); //search start vertex in 
                                                    //those vertexes that we already have
                for(j=0;EendV!=GM.Vertex[j];j++);   //search end vertex in ...
                GM.EdgeWeight[i][j]=weight;    //save weight in corresponding position
                if(GM.GType==0) //if graph is undirected 
                {
                    GM.EdgeWeight[j][i]=weight; //save data diagonally
                }
            }
        }
        static void ClearGraph(GraphMatrix2 GM)
        {
            int i,j;
            for(i=0;i<GM.VertexNum;i++)
            {
                for(j=0;j<GM.VertexNum;j++)
                {
                    GM.EdgeWeight[i][j]=MaxValue;
                }
            }
        }
        static void DisplayGraph(GraphMatrix2 GM)
        {
            int i,j;
            for(j=0;j<GM.VertexNum;j++)
            {
                System.out.printf("\t%c",GM.Vertex[j]); //print vertex at the first line
            }
            System.out.printf("\n");
            for(i=0;i<GM.VertexNum;i++)
            {
                System.out.printf("%c", GM.Vertex[i]);
                for(j=0;j<GM.VertexNum;j++) 
                {
                    if(GM.EdgeWeight[i][j]==MaxValue)
                    {
                        System.out.printf("\tz");//z means infinity here
                    }else
                    {
                        System.out.printf("\t%d", GM.EdgeWeight[i][j]);
                    }
                }System.out.printf("\n");
            }
        }
        static void DistMin(GraphMatrix2 GM,int vend)
        {
            int[] weight = new int[GraphMatrix2.MaxNum];
            int i,j,k,min;
            vend--;
            
            for(i=0;i<GM.VertexNum;i++)
            {
                weight[i]=GM.EdgeWeight[vend][i];
            }
            for(i=0;i<GM.VertexNum;i++)
            {
                if(weight[i]<MaxValue && weight[i]>0)
                {
                    path[i]=vend;
                }
            }
            for(i=0;i<GM.VertexNum;i++)
            {
                tmpvertex[i]=0;
            }
            tmpvertex[vend]=1;
            weight[vend]=0;
            for(i=0;i<GM.VertexNum;i++)
            {
                min=MaxValue;
                k=vend;
                for(j=0;j<GM.VertexNum;j++)
                {
                    if(tmpvertex[j]==0 && weight[j]<min)
                    {
                        min=weight[j];
                        k=j;
                    }
                }
                tmpvertex[k]=1;
                for(j=0;j<GM.VertexNum;j++)
                {
                    if(tmpvertex[j]==0 && weight[k]+GM.EdgeWeight[k][j]<weight[j])
                    {
                        weight[j]=weight[k]+GM.EdgeWeight[k][j];
                        path[j]=k;
                    }
                }
            }
        }
        public static void main(String[] args)
        {
            GraphMatrix2 GM = new GraphMatrix2();
            int vend;
            int i,k;
            System.out.println("enter the type of graph:");
            GM.GType=input.nextInt();
            System.out.println("enter the number of vertex:");
            GM.VertexNum=input.nextInt();
            System.out.println("enter the number of edge:");
            GM.EdgeNum=input.nextInt();
            ClearGraph(GM);
            CreateGraph(GM);
            System.out.println("the adjacency matrix of this graph is below:");
            DisplayGraph(GM);
            
            System.out.println("enter the destination vertex");
            vend = input.nextInt();
            
            DistMin(GM,vend);
            
            vend--;
            System.out.printf("the shortest path to vertex %c is:", GM.Vertex[vend]);
            for(i=0;i<GM.VertexNum;i++)
            {
                if(tmpvertex[i]==1)
                {
                    k=i;
                    while(k!=vend)
                    {
                        System.out.printf("vertex %c -", GM.Vertex[k]);
                        k=path[k];
                    }
                    System.out.printf("vertex %c \n", GM.Vertex[k]);
                }
                else
                {
                    System.out.printf("%c - %c:no path\n",GM.Vertex[i],GM.Vertex[vend]);
                    
                }
            }
                
        }
}