#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <fstream>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;
#define NULL_VALUE -999999
#define INFINITY 999999
#define WHITE 1
#define GREY 2
#define BLACK 3
#define MAX_HEAP_SIZE 100000


#define MAXREAL 999999.0

class Queue
{
    int queueInitSize ;
    int queueMaxSize;
    int * data;
    int length;
    int front;
    int rear;
public:
    Queue();
    ~Queue();
    void enqueue(int item); //insert item in the queue
    int dequeue(); //returns the item according to FIFO
    bool empty(); //return true if Queue is empty
};

Queue::Queue()
{
    queueInitSize = 2 ;
    queueMaxSize = queueInitSize;
    data = new int[queueMaxSize] ; //allocate initial memory
    length = 0 ;
    front = 0;
    rear = 0;
}


void Queue::enqueue(int item)
{
    if (length == queueMaxSize)
    {
        int * tempData ;
        //allocate new memory space for tempList
        queueMaxSize = 2 * queueMaxSize ;
        tempData = new int[queueMaxSize] ;
        int i, j;
        j = 0;
        for( i = rear; i < length ; i++ )
        {
            tempData[j++] = data[i] ; //copy items from rear
        }
        for( i = 0; i < rear ; i++ )
        {
            tempData[j++] = data[i] ; //copy items before rear
        }
        rear = 0 ;
        front = length ;
        delete[] data ; //free the memory allocated before
        data = tempData ; //make list to point to new memory
    }

    data[front] = item ; //store new item
    front = (front + 1) % queueMaxSize ;
    length++ ;
}


bool Queue::empty()
{
    if(length == 0) return true ;
    else return false ;
}


int Queue::dequeue()
{
    if(length == 0) return NULL_VALUE ;
    int item = data[rear] ;
    rear = (rear + 1) % queueMaxSize ;
    length-- ;
    return item ;
}


Queue::~Queue()
{
    if(data) delete[] data; //deallocate memory
    data = 0; //set to NULL
}

//****************Queue class ends here************************

//****************Dynamic ArrayList class based************************
class ArrayList
{
    int * list;
    int length ;
    int listMaxSize ;
    int listInitSize ;
public:
    ArrayList() ;
    ~ArrayList() ;
    int searchItem(int item) ;
    void insertItem(int item) ;
    void removeItem(int item) ;
    void removeItemAt(int item);
    int getItem(int position) ;
    int getLength();
    bool empty();
    void printList();
} ;


ArrayList::ArrayList()
{
    listInitSize = 2 ;
    listMaxSize = listInitSize ;
    list = new int[listMaxSize] ;
    length = 0 ;
}

void ArrayList::insertItem(int newitem)
{
    int * tempList ;
    if (length == listMaxSize)
    {
        //allocate new memory space for tempList
        listMaxSize = 2 * listMaxSize ;
        tempList = new int[listMaxSize] ;
        int i;
        for( i = 0; i < length ; i++ )
        {
            tempList[i] = list[i] ; //copy all items from list to tempList
        }
        delete[] list ; //free the memory allocated before
        list = tempList ; //make list to point to new memory
    };

    list[length] = newitem ; //store new item
    length++ ;
}

int ArrayList::searchItem(int item)
{
    int i = 0;
    for (i = 0; i < length; i++)
    {
        if( list[i] == item ) return i;
    }
    return NULL_VALUE;
}

void ArrayList::removeItemAt(int position) //do not preserve order of items
{
    if ( position < 0 || position >= length ) return ; //nothing to remove
    list[position] = list[length-1] ;
    length-- ;
}


void ArrayList::removeItem(int item)
{
    int position;
    position = searchItem(item) ;
    if ( position == NULL_VALUE ) return ; //nothing to remove
    removeItemAt(position) ;
}


int ArrayList::getItem(int position)
{
    if(position < 0 || position >= length) return NULL_VALUE ;
    return list[position] ;
}

int ArrayList::getLength()
{
    return length ;
}

bool ArrayList::empty()
{
    if(length==0)return true;
    else return false;
}

void ArrayList::printList()
{
    int i;
    for(i=0; i<length; i++)
        printf("%d ", list[i]);
    printf("Current size: %d, current length: %d\n", listMaxSize, length);
}

ArrayList::~ArrayList()
{
    if(list) delete [] list;
    list = 0 ;
}

//******************ArrayList class ends here*************************

//******************Graph class starts here**************************
class Graph
{
public:
    int nVertices, nEdges ;
    bool directed ;
    ArrayList  * adjList ;
    //define other variables required for bfs such as color, parent, and dist
    //you must use pointers and dynamic allocation
    int *color;
    int *dist;
    int *parent;
    int time;
    int *discoveryTime;
    int *finishTime;
    int **weightArray;
    int **distance;
    int **path;

    Graph(bool dir = false);
    ~Graph();
    void setnVertices(int n);
    void addEdge(int u, int v);
    void removeEdge(int u, int v);
    bool isEdge(int u, int v);
    int getDegree(int u);
    bool hasCommonAdjacent(int u, int v);
    int getDist(int u, int v);
    void printGraph();
    void bfs(int source); //will run bfs in the graph
    void dfs(); //will run dfs in the graph
    void dfs_visit(int u);
    void makeTranspose();
    void makeUndirected();
    void FloydWarshallAlgo();
};


Graph::Graph(bool dir)
{
    nVertices = 0 ;
    nEdges = 0 ;
    adjList = 0 ;
    directed = dir ; //set direction of the graph
    color = 0;
    dist = 0;
    parent = 0;
    discoveryTime = 0;
    finishTime = 0;
    //define other variables to be initialized
}

void Graph::setnVertices(int n)
{
    this->nVertices = n ;
    if(adjList!=0) delete[] adjList ; //delete previous list
    adjList = new ArrayList[nVertices] ;
    weightArray = (int **) malloc(nVertices * sizeof(int *));

    for (int i = 0; i < nVertices; i++)
    {
        weightArray[i] = (int *) malloc(nVertices * sizeof(int));
    }

    for (int i = 0; i < nVertices; i++){
        for(int j=0;j<nVertices;j++)
    {
        if(i==j)  weightArray[i][j] = 0;
       else  weightArray[i][j] = 99999;
    }
    }

     distance = (int **) malloc(nVertices * sizeof(int *));

    for (int i = 0; i < nVertices; i++)
    {
        distance[i] = (int *) malloc(nVertices * sizeof(int));
    }
   for (int i = 0; i < nVertices; i++){
        for(int j=0;j<nVertices;j++)
    {
          if(i==j)  distance[i][j] = 0;

       else distance[i][j] = 99999;
    }
    }
   path = (int **) malloc(nVertices * sizeof(int *));

    for (int i = 0; i < nVertices; i++)
    {
        path[i] = (int *) malloc(nVertices * sizeof(int));
    }
    for (int i = 0; i < nVertices; i++){
        for(int j=0;j<nVertices;j++)
    {
        path[i][j] = 99999;
    }
    }
    parent = new int[nVertices];
}

void Graph::addEdge(int u, int v)
{
    if(u<0 || v<0 || u>=nVertices || v>=nVertices) return; //vertex out of range
    this->nEdges++ ;
    adjList[u].insertItem(v) ;
    if(!directed) adjList[v].insertItem(u) ; //undirected holee
}




void Graph::FloydWarshallAlgo(){

    for (int i = 0; i < nVertices ; i++){
        for (int j = 0; j < nVertices; j++){
            distance[i][j] = weightArray[i][j];
             if (distance[i][j] != 99999 && i != j) {
                    path[i][j] = i;
                } else {
                    path[i][j] = -1;
                }
        }
}

    for(int k=0; k < nVertices; k++){
            for(int i=0; i <nVertices; i++){
                for(int j=0; j < nVertices; j++){
                    if(distance[i][k] == 99999 || distance[k][j] == 99999) {
                        continue;
                    }
                    if(distance[i][j] > distance[i][k] + distance[k][j]){
                        distance[i][j] = distance[i][k] + distance[k][j];
                        path[i][j] = path[k][j];

                    }
                }
            }
        }
        for(int i = 0; i < nVertices; i++) {
            if(distance[i][i] < 0) {
                  cout << "Negative cycle present"  ;
            }
        }
                for (int i = 0; i < nVertices ; i++){
                        for (int j = 0; j < nVertices; j++)
                        {
                            if(weightArray[i][j]==99999)  cout<< "INF" <<" ";
                             else
                               cout<< weightArray[i][j]<<" ";
                        }
                        cout <<endl;

                }
                 for (int i = 0; i < nVertices ; i++){
                        for (int j = 0; j < nVertices; j++)
                        {
                            if(distance[i][j]==99999)  cout<< "INF" <<" ";
                             else  cout << distance[i][j]<<" ";
                        }
                        cout << endl;

                }
                 for (int i = 0; i < nVertices ; i++){
                        for (int j = 0; j < nVertices; j++)
                        {
                             if(path[i][j]==-1)  cout<< "INF" <<" ";
                             else
                               cout<< path[i][j]+1<<" ";
                        }
                        cout <<endl;

                }

                 int i=0;
                 int j=1;
                            cout << "path between" << i+1 << " " << j+1<<endl;
                            stack <int> Stack;
                            Stack.push(j);
                            cout << j+1<<" ";
                            int a = i;
                            int b = j;
                            while (true) {

                                    b = path[a][b];
                                    if(b == -1) {
                                        return;
                                    }
                                    Stack.push(b);
                                    cout << b+1<<" ";
                                    if(b == a) {
                                        break;
                                    }

                            }
                           /// (u,v) edge thaktei hobe
                            /// (p,q) er majhe notun path ber korte hobe jetate (u,v) thakbe
                            int u=0;
                            int v=2;
                            int p=0;
                            int q=3;
//  for (int i = 0; i < nVertices ; i++){
//        for (int j = 0; j < nVertices; j++){
//            distance[i][j] = weightArray[i][j];
//
//        }
//}

    for(int k=0; k < nVertices; k++){

                   // if(distance[i][j] > distance[i][p] + distance[p][q]+distance[q][j]){
                        distance[p][q] = distance[p][u] + weightArray[u][v]+distance[v][q];
                     //   path[i][j] = path[k][j];


        }
        cout << "dis:   "<<distance[p][q];
//            for(int k=0; k < nVertices; k++){
//                    if(distance[p][k] == 99999 || distance[k][q] == 99999) {
//                        continue;
//                    }
//                    if(distance[p][q] > distance[p][u] +distance[u][v]+distance[v][q]){
//                        distance[p][q] =distance[p][u] +distance[u][v]+distance[v][q];
//
//                    }
//                }
//                cout << "new dist: "<<distance[i][j];


//                            while(!Stack.empty()){
//                                int a = Stack.pop();
//                                    printf("%d ",a);
//                            }




}
void Graph::printGraph()
{
    printf("\nNumber of vertices: %d, Number of edges: %d\n", nVertices, nEdges);
    for(int i=0; i<nVertices; i++)
    {
        printf("%d:", i+1);
        for(int j=0; j<adjList[i].getLength(); j++)
        {
            printf(" %d", adjList[i].getItem(j)+1);
        }
        printf("\n");
    }
}

Graph::~Graph()
{
    //write your destructor here
    delete [] color;
    delete [] dist;
    delete [] parent;
    delete [] finishTime;
    delete [] discoveryTime;
    delete [] adjList;
}


//**********************Graph class ends here******************************


//******main function to test your code*************************
int main(void)
{
    int n,m;
    ifstream in ("testcasefloyd.txt");
    Graph g(true);
    int u,v,w;
    // scanf("%d", &n);
    in >> n;
    in >> m;
    g.setnVertices(n);
//    g.setnEdges(m);
    for(int i=0; i<m; i++)
    {
        in >> u;
        in >> v;
        in >> w;
        if      ( g.weightArray[u-1][v-1]==-1)
        {
            g.weightArray[u-1][v-1] = w;
            if(g.directed==false)  g.weightArray[v-1][u-1] = w;
            g.addEdge(u-1,v-1);
        }
        else if(g.weightArray[u-1][v-1]>w)
        {
            g.weightArray[u-1][v-1] = w;
            if(g.directed==false)       g.weightArray[v-1][u-1] = w;
             g.addEdge(u-1,v-1);
        }
    }
    g.FloydWarshallAlgo();

//g.printGraph();

// Graph MST =

    return 0;

}