// Zestaw zadania 2,3,5 PS0506
#include <iostream> //basic stream
#include <random>   //random gen
#include <fstream>  //files
#include <cstdlib>   //wowowowo
#include <queue>
using namespace std;//namespace
/* functions headers
 */
void OdczytPlecak(int n,int *p,int *w); //wczytuje dane o przedmiotach do tablic
void OdczytPlecak(int &n,int &w); //odczytuje udzwig i ilosc przedmiotow
void AlgorytmPlecak(int *p,int *w, int n, int W);//glowny algorytm
void GetDijkstra(int &n,int &u);
void GetDijkstra(int **tab);
void SaveDijkstra(int n,int *dist,int *pred);
void AlgorytmDijkstra(int s,int n,int **A,int *dist,int *pred);
int findi(int i, int parent[]);
void onion(int parent[], int x, int y);
/* classes
 */
/* main
 */
int main(int argc, char const *argv[]) {
        system("clear");
        /**/
        //Plecak
        /**/
        int m,W;
        // n to liczba przedmiotow mozliwych do zebrania
        // w to udzwig plecaka

        OdczytPlecak(m,W); // odczyt ilosci przedmiotow i udzwigu

        // inicjalizacja tablic
        int *p = new int[m];
        int *w = new int[m];

        OdczytPlecak(m,p,w); // wczytanie danych o przedmiotach do tablicy

        AlgorytmPlecak(p,w,m,W); // glowny AlgorytmPlecak


        //zwolnienie pamieci po tablicach dynamicznych
        delete[] p;
        delete[] w;
        /**/
        //Dijkstra
        /**/
        //Pozyskanie danych wejsciowych
        int n,u;
        GetDijkstra(n,u);
        /**/
        // Inicjalizacj tablic
        int **tab;
        int *dist;
        int *pred;
        tab = new int * [n+1];
        for(int i=0; i<n+1; i++) {tab[i] = new int [n+1];}
        dist = new int[n+1];
        pred = new int[n+1];
        /**/
        //Wypelnienie tablicy danymi z pliku tekstowego
        GetDijkstra(tab);
        /**/
        //Glowny AlgorytmDijkstra
        AlgorytmDijkstra(u,n,tab,dist,pred);
        /**/
        //Zapis tablic pred i dist do pliku tekstowego
        SaveDijkstra(n,dist,pred);
        /**/
        // Zwalnianie pamieci po tablicach
        for(int i=0; i<n+1; i++) {delete [] tab[i];}
        delete [] tab;
        delete [] dist;
        delete [] pred;
        /**/
        /**/
        //Kruskal
        /**/
        //Pozyskanie danych wejsciowych4
        int n2,m2;
        ifstream plik("In0303.dll");
        if(plik.fail())
                cout << "error" << endl;
        plik>>n2; //ilosc wierzcholkow
        plik>>m2; //ilosc krawedzi
        priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >,greater <pair<int,pair<int,int> > > > que;
        int pom,pom2; //pom do ktorego, pom2 za ile(koszt)
        int zap,i=1;
        plik>>pom>>pom2;
        que.push(make_pair(pom2,make_pair(i,pom)));
        zap=pom;

        while(!plik.eof()) {
                plik>>pom>>pom2;
                if(pom>zap) {
                        que.push(make_pair(pom2,make_pair(i,pom)));

                        zap=pom;
                }
                else {
                        i++;
                        que.push(make_pair(pom2,make_pair(i,pom)));

                        zap=pom;
                }
        }
        plik.close();
        pair<int,pair<int,int> > pomm;
        vector<int> pomv;
        int sum=0;
        int odw[n2+1];
        for(int i=0; i<=n2; i++) odw[i] = i;
        while(!que.empty()) {
                pomm = que.top();

                if(findi(pomm.second.first,odw)!=findi(pomm.second.second,odw)) {
                        onion(odw,pomm.second.first,pomm.second.second);
                        pomv.push_back(pomm.second.first);
                        pomv.push_back(pomm.second.second);
                        pomv.push_back(pomm.first);
                        sum+=pomm.first;
                }
                que.pop();
        }

        fstream plikk;
        plikk.open("Out0303.dll",ios::out);
        plikk<<sum<<endl;
        for(int i=0; i<pomv.size(); i++) {
                if((i+1)%3==0) {
                        plikk<<"["<<pomv[i]<<"], ";
                }
                else{
                        plikk<<pomv[i]<<" ";
                }
        }
        plikk.close();
        return 0;
}
/* functions bodies
 */
void OdczytPlecak(int n,int *p,int *w){
        ifstream plik("In0302.dll");
        if(plik.fail())
                cout << "error" << endl;
        int pom;
        plik>>pom>>pom;
        for(int i=0; i<n; i++) {
                plik>>p[i];
                plik>>w[i];
        }
        plik.close();
}
void OdczytPlecak(int &n,int &w){
        ifstream plik("In0302.dll");
        if(plik.fail())
                cout << "error" << endl;
        plik>>n; // ilosc przedmiotow ktore mozesz zebrac
        plik>>w; // udzwig plecaka
        plik.close();
}
void AlgorytmPlecak(int *p,int *w, int n, int W){
        int pom;
        int S1[W+1][n+1];
        int S2[W+1][n+1];
        // generowanie tablic S1 oraz S2
        for(int i=0; i<=W; i++) {
                S1[i][0]=0; S2[i][0]=0;
        }
        for(int i=0; i<n+1; i++) {
                S1[0][i]=0; S2[0][i]=0;
        }
        for(int i=1; i<=W; i++) {
                for(int j=1; j<=n; j++)
                {
                        S2[i][j]=0;
                }
        }
        for(int i=1; i<=W; i++) {
                for(int j=1; j<=n; j++) {
                        if(i-w[j-1]>=0) {
                                pom=S1[i-w[j-1]][j-1]+p[j-1];
                                if(pom<S1[i][j-1]) {
                                        S1[i][j]=S1[i][j-1];
                                }
                                else{
                                        S1[i][j]=pom;
                                        S2[i][j]=1;
                                }
                        }
                        else  {
                                S1[i][j]=S1[i][j-1];
                        }
                }
        }
        //zapis do pliku
        fstream plik("Out0302.dll",ios::out);
        int maks=0,j1,pomocnicza;
        for(int i=1; i<=W; i++)
        {
                for(int j=1; j<=n; j++)
                {
                        if(S1[i][j]>maks)
                                maks=S1[i][j];
                }
        }
        for(int i=1; i<=W; i++) {
                for(int j=1; j<=n; j++)  {
                        if(S1[i][j]==maks)    {
                                pomocnicza=maks;
                                j1=j;
                                plik<<j1<<" ";
                                while(pomocnicza>0)    {
                                        pomocnicza-=w[j1-1];
                                        while(S1[pomocnicza][j1]==S1[pomocnicza][j1-1])
                                                j1-=1;
                                        if(j1==0) break;
                                        plik<<j1<<" ";
                                }
                                plik<<endl;
                        }
                }
        }
        plik.close();
}
void GetDijkstra(int &n,int &u){
        ifstream plik("In0305.dll");
        if(plik.fail())
                cout << "error" << endl;
        plik>>n; //ilosc wierzcholkow
        plik>>u; //adres ujscia
        plik.close();
}
void GetDijkstra(int **tab){
        ifstream plik("In0305.dll");
        int n,u;
        if(plik.fail())
                cout << "error" << endl;
        plik>>n; //ilosc wierzcholkow
        plik>>u; //adres ujscia
        for(int j=1; j<=n; j++) {
                for(int i=1; i<=n; i++) {
                        plik >> tab[i][j];
                }
        }
        plik.close();
}
void SaveDijkstra(int n,int *dist,int *pred){
        fstream plik;
        plik.open("Out0305.dll",ios::out);
        plik<<"dist[";
        for(int i=1; i<=n; i++) {plik<<dist[i]<<" ";}
        plik<<"]"<<endl;
        plik<<"pred[";
        for(int i=1; i<=n; i++) {plik<<pred[i]<<" ";}
        plik<<"]";
        plik.close();
}
void AlgorytmDijkstra(int s,int n,int **A,int *dist,int *pred){
        int pom; //pom
        //graf od 1, nie od 0
        for(int i=1; i<=n; i++) dist[i] = 214783647; //-1 = inf
        dist[n] = 0;
        for(int i=1; i<=n; i++) pred[i] = -1;
        priority_queue< pair<int,int>, vector<pair<int,int> >,greater <pair<int,int> > > que;
        //priority_queue<int> -> deklaracja kolejki priorytetowej
        //  priority_queue< pair<int,int>, vector<pair<int,int> >,greater <pair<int,int> > > que ->
        //  deklaracja kolejki priortetowej rosnacej zawierajacej pary, pary sortuje najpierw po .first ,jesli rowny to po .second
        que.push(make_pair(0,s)); //dodajemy wierzcholek startowy, waga=0, id wierzcholka = s (startowy)
        //que.top().second=id_wierzcholka, j=id_sasiad.pl
        while(!que.empty()) {
                pom=que.top().second;
                for(int j=1; j<=n; j++) { // sprawdza czy dla pom wierzcholka istnieje sasiad
                        if(A[pom][j]!=-1) { // \/istnieje droga
                                if((dist[pom]+A[pom][j])<dist[j]) { // jezeli droga sie poprawia to jest aktualizowana
                                        pred[j]=pom; // z tego wierzchloka obecnie jest najbardziej optylalna droga
                                        dist[j]=dist[pom]+A[pom][j]; // aktaulizacja sumy wag drogi
                                        que.push(make_pair(dist[j],j));
                                }
                        }
                }
                que.pop();
        }
}
int findi(int i, int parent[])
{
        if (parent[i] == i)
                return i;
        return findi(parent[i], parent);
}
void onion(int parent[], int x, int y)
{
        int xset = findi(x, parent);
        int yset = findi(y, parent);
        parent[xset] = yset;
}