package gojabe;
import java.io.*;
public class djkistras_algorithm {
       public static void main(String args[])throws Exception
       {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("No of points to be dealt with ::");
        int n=Integer.parseInt(br.readLine());
        int v[][]=new int[n][n];
        int i=0,j=0,k=0;
        while(true)
        {
             System.out.println("Enter the coordinates along with the distances (Pt. A,Pt. B,Distance)::");
             String s= br.readLine();
             if(s.equals("over"))
                 break;
             String data[]=s.split(",");
             i=Integer.parseInt(data[0]);
             j=Integer.parseInt(data[1]);
             k=Integer.parseInt(data[2]);
             if(v[i-1][j-1]==0)
             {
                 v[i-1][j-1]=k;
                 v[j-1][i-1]=k;
             }
        }
                System.out.println("Enter the vertex from which shortest path to all other vertex is goin to be calculated:");
                k=Integer.parseInt(br.readLine());
        djikstra(v,n,k-1);
    }
    
    public static void djikstra(int x[][],int n,int v)
    {
        int W[][]=new int[n][n];
        int dist[]=new int[n];
        int i=0,j=0,k=0;
        String path[]=new String[n];
        W=x;
        for(i=0;i<n;i++)
            W[i][i]=0;
        for(i=0;i<n;i++)
        {
            if(v==i)
            {
                dist[v]=0;
                path[i]=(v+1)+"->"+(v+1);
            }
            else if(W[v][i]>0)
            {
                dist[i]=W[v][i];
                path[i]=(v+1)+"->"+(i+1);
            }
            else
            {
                path[i]=(v+1)+"";
            }
            W[i][v]=0;
            W[v][i]=0;
        }
        for(i=0;i<n;i++)
            if(dist[i]>0 )
            for(j=0;j<n;j++)
            {
                if(W[i][j]>0){
                if(dist[j]==0 && j!=v)
                {
                    dist[j]=dist[i]+W[i][j];
                    path[j]=path[i]+"->"+(j+1);
                }
                else if(dist[j]>0 && (dist[i]+W[i][j])<dist[j])
                {
                   dist[j]=dist[i]+W[i][j];
                   path[j]=path[i]+"->"+(j+1);
                }
                }
            }
               
        display(dist,path,n);
    }
    public static void display(int dist[],String path[],int n)
    {
        System.out.println("Stortest possible path::");
        for(int i=0;i<n;i++)
            System.out.println(path[i]+" = "+dist[i]);
    }
    
}