Đỗ Trần Minh Huy

#include <iostream>

#include <stack>

#define MAX 100

#define VOCUC 1000

int LuuVet[MAX];

int ChuaXet[MAX];

int DoDaiDuongDiToi[MAX];

int SAU_NUT[MAX][MAX];

int L[MAX][MAX];

struct DOTHI {

    int n;

    int a[MAX][MAX];

};

void DStoMTK(DOTHI &g) {

    int m;

    std::cin >> g.n >> m;

    for (int i = 1; i <= g.n; i++) {

        for (int j = 1; j <= g.n; j++) {

            g.a[i][j] = 0;

        }

    }

    int u, v, w;

    for (int i = 1; i <= m; i++) {

        std::cin >> u >> v >> w;

        g.a[u][v] = w;

    }

}

int TimDuongDiNhoNhat(DOTHI g) {

    int li = -1;

    float p = VOCUC;

    for (int i = 1; i <= g.n; i++) {

        if (ChuaXet[i] == 0 && DoDaiDuongDiToi[i] < p) {

            p = DoDaiDuongDiToi[i];

            li = i;

        }

    }

    return li;

}

void CapNhatDuongDi(int u, DOTHI g) {

    ChuaXet[u] = 1;

    for (int v = 1; v <= g.n; v++) {

        if (ChuaXet[v] == 0 && g.a[u][v] > 0 && g.a[u][v] < VOCUC)

            if (DoDaiDuongDiToi[v] > DoDaiDuongDiToi[u] + g.a[u][v]) {

                DoDaiDuongDiToi[v] = DoDaiDuongDiToi[u] + g.a[u][v];

                LuuVet[v] = u;

            }

    }

}

void Dijkstra(int S, int F, DOTHI g) {

    std::stack<int> temp;

    for (int i = 1; i <= g.n; i++) {

        ChuaXet[i] = 0;

        DoDaiDuongDiToi[i] = VOCUC;

        LuuVet[i] = -1;

    }

    DoDaiDuongDiToi[S] = 0;

    while (ChuaXet[F] == 0) {

        int u = TimDuongDiNhoNhat(g);

        if (u == -1) break;

        CapNhatDuongDi(u, g);

    }

    if (ChuaXet[F] == 1) {

        temp.push(F);

        int i = LuuVet[F];

        while (i != -1) {

            temp.push(i);

            i = LuuVet[i];

        }

        std::cout << DoDaiDuongDiToi[F] << std::endl;

        while (!temp.empty()) {

            std::cout << temp.top() << " ";

            temp.pop();

        }

    } else

        std::cout << "-1";

}

void Floyd(DOTHI g) {

    std::stack<int> temp;

    for (int i = 1; i <= g.n; i++) {

        for (int j = 1; j <= g.n; j++) {

            if (g.a[i][j] > 0) {

                SAU_NUT[i][j] = j;

                L[i][j] = g.a[i][j];

            } else {

                SAU_NUT[i][j] = -1;

                L[i][j] = VOCUC;

            }

        }

    }

    for (int k = 1; k <= g.n; k++) {

        for (int i = 1; i <= g.n; i++) {

            for (int j = 1; j <= g.n; j++) {

                if (L[i][j] > L[i][k] + L[k][j]) {

                    L[i][j] = L[i][k] + L[k][j];

                    SAU_NUT[i][j] = SAU_NUT[i][k];

                }

            }

        }

    }

    int startVertex, targetVertex;

    std::cin >> startVertex >> targetVertex;

    if (SAU_NUT[startVertex][targetVertex] == -1) {

        std::cout << "-1";

    } else {

        std::cout << L[startVertex][targetVertex] << std::endl;

        std::cout << startVertex << " ";

        int u = startVertex;

        while (SAU_NUT[u][targetVertex] != targetVertex) {

            u = SAU_NUT[u][targetVertex];

            std::cout << u << " ";

        }

        std::cout << targetVertex << " ";

    }

}

int main() {

    DOTHI g;

    DStoMTK(g);

    //int startVertex, targetVertex;

    //std::cin >> startVertex >> targetVertex;

  //  Dijkstra(startVertex, targetVertex, g);

    Floyd(g);

    return 0;

}