#include <bits/stdc++.h>

using namespace std;

int main()
{
    int v;
    cout<<"\nEnter the number of vertices: ";
    cin>>v;
    int adj[v][v];
    long dist[v][v];
    int next[v][v];

    for(auto i=0;i<v;i++)
        for(auto j=0;j<v;j++)
            cin>>adj[i][j];

    for(auto i=0;i<v;i++)
    {
        for(auto j=0;j<v;j++)
        {
            if(i==j)
            {
                dist[i][j]=0;
                next[i][j]=i;
            }
            else if(adj[i][j])
            {
                dist[i][j] = adj[i][j];
                next[i][j] = j;
            }
            else
            {
                dist[i][j] = INT_MAX;
                next[i][j] = -1;
            }
        }
    }

    for(auto k=0;k<v;k++)
        for(auto i=0;i<v;i++)
            for(auto j=0;j<v;j++)
            {
                if(dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
    cout<<"\nThe Shortest Distances are: \n";

    for(auto i=0;i<v;i++)
    {
       for(auto j=0;j<v;j++)
        {
            cout<<dist[i][j]<<" ";
        }
        cout<<"\n";
    }

    cout<<"\nThe Shortest Paths are: \n";
      // for printing path
      for(int i=0;i<v;i++)
      {
        for(int j=i+1;j<v;j++)
        {
          int u=i,v=j;
          cout<<u;
          while(u!=v)
          {
            u=next[u][v];
            cout<<"->"<<u;
          }
          cout<<"\n";
        }
      }
}