#include <iostream>
#include <sstream>
#include <fstream>
#define inf 9999
using namespace std;
//---zmienne_globalne----
struct Edge
{
    int weight;
    int beg;
    int end;
}*E;
int n,m;
int *bell;
//-----------------------
void wczytaj(void);
bool Bellman(Edge *e,int wielkosc , int licznik);
void zmiana_wag(Edge *e, int *h,int m);
int *Dijkstry(int s, int n);
void finalizacja(int *h , int **q2);

int main()
{
    wczytaj();

    for(int i=0; i<m; i++)
    {
        cout<<E[i].beg<<" "<<E[i].end<<" "<<E[i].weight <<endl;
    }
    cout<<endl;
    cout<<m<<endl;
    bool wykonaj;
    int *q=new int[n+1];
    int **q2=new int*[n];

    wykonaj=Bellman(E,n+1, m);
    if(wykonaj==true){
       int *h=bell;
    zmiana_wag(E,h, m);

    for(int i=0;i<=n;i++){
        q2[i]=Dijkstry(i, n);
    }

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            cout<<q2[i][j]<<" ";
        }
        cout<<endl;
    }

    finalizacja(h,q2);

     //----zwolnienie pamieci----
    for(int i=0;i<n+1;i++){
        delete [] q2[i];
    }

    delete [] h;

    }
   else{
    cout<<"Algorytm Johnsona nie zadzia³a";
   }
    delete [] q;
    delete [] *q2;






}
bool Bellman(Edge *e, int wielkosc, int m)
{
    bell=new int [wielkosc];
    for(int i=0; i<wielkosc; i++)bell[i]=0;
    bool sprawdz=false;
    while(!sprawdz)
    {
        sprawdz=true;
        for(int i=0; i<m; i++)
        {
            if(bell[e[i].end]>bell[e[i].beg]+e[i].weight)
            {
                bell[e[i].end]=bell[e[i].beg]+e[i].weight;
                sprawdz=false;
            }
        }
    }

    for(int i=0;i<m;i++){
        if(bell[e[i].end]>(bell[e[i].beg]+e[i].weight))return false;
    }
return true;
}



int *Dijkstry(int s, int n)
{
    //-------tworzenie macierzy wag-----------
    int **A=new int*[n+1];
    for(int i=0;i<=n;i++)A[i]=new int[n+1];

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
                if(i==j){
                    A[i][j]=0;
                }
                else{
                    A[i][j]=inf;
                }

        }
    }
    for(int i=0;i<m;i++){
        A[E[i].beg][E[i].end]=E[i].weight;
    }

 /*   for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
                cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }*/
//----------------------------------------------

    int *dist=new int[n+1];
    int *pred=new int[n+1];

    int* fin = new int[n+1];
	for (int v = 0; v <= n; v++) {
		dist[v] = inf;
		fin[v] = 0;
		pred[v] = -1;
	}
	dist[s] = 0;
	fin[s] = 1;
	int last = s, y = 0, temp = inf;

	for (int i = 1; i < n; i++) {
		for (int v = 0; v <= n; v++) {
			if ((A[last][v] < inf) && (fin[v] == 0)) {
				if (dist[last] + A[last][v] < dist[v]) {
					dist[v] = dist[last] + A[last][v];
					pred[v] = last+1;
				}
			}
			temp = inf;
			y = 0;
			for (int u = 0; u < n; u++) {
				if ((fin[u] == 0) && (dist[u] < temp)) {
					y = u;
					temp = dist[u];
				}
			}
		}
		if (temp < inf) {
			fin[y] = 1;
			last = y;
		}
	}

	delete[] fin;

  //  cout<<endl<<"!";
   // for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
    return dist;

}
void zmiana_wag(Edge *e, int *h, int m)
{
    for(int i=0; i<m; i++)
    {
        e[i].weight=e[i].weight+h[e[i].beg]-h[e[i].end];
    }
}
void finalizacja(int *h, int **q2)
{

    int **D=new int*[n];
    for(int i=0;i<n;i++){
        D[i]=new int[n];
    }

   cout<<endl;
   for(int i=0;i<=n;i++)cout<<h[i]<<" ";
   cout<<endl;
     cout<<endl;
       for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
                if(q2[i+1][j+1]==inf || h[j+1]==inf || h[i+1]==inf){
                    D[i][j]=inf;
                }
                else{
                    D[i][j]=q2[i+1][j+1]+h[j+1]-h[i+1];
                }


       }
    }
    //----zapis------
    ofstream out;
    out.open("Out0502.txt");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            out<<D[i][j]<<" ";
        }
        out<<'\n';
    }
    out.close();
    //------zwolnienie pamieci----
    for(int i=0;i<n;i++){
        delete [] D[i];
    }
    delete [] *D;

}
    void wczytaj(void)
    {
        int i=0, licznik=0,sumka=0,s=0;
        ifstream wej;
        wej.open("In0502.txt");
        int pom2[100]= {0};
        string pom;
        while(!wej.eof())
        {
            getline(wej,pom);
            sumka=0;
            for(int k=0; k<pom.size(); k++)
            {

                if(pom[k]==' ')
                {
                    sumka++;
                    licznik++;
                }
            }
            pom2[i]=sumka+1;
            if(pom.size()>0)
            licznik++;
            sumka=0;
            i++;
        }
        wej.close();
        wej.open("In0502.txt");
        wej>>n;
        int x=1;
        licznik=licznik/2;
        E = new Edge[licznik];
        m=licznik;
        i=0;
        while(!wej.eof())
        {
            for(int j=1; j<pom2[x]; j=j+2)
            {

                wej>>E[i].end;
                wej>>E[i].weight;
                E[i].beg=x;
                i++;
            }
            x++;
        }

    }