#include <bits/stdc++.h>

using namespace std;

#define N 100
#define INITFITE 32767

typedef struct node{
    int vernum, arcnum;
    char data[N];
    int martrix[N][N];
}Graph;

struct nnode{
    int pree;
    int lowcost;
}Closedge[N];

int locate(Graph G,char ch){
    for(int i = 0;i < N;i++){
        if(G.data[i] == ch)
            return i;
    }
    return 0;
}

void Create_Graph(Graph &G){
    char v1, v2;
    int weight;
    cout << "请输入节点数" << endl;
    cin >> G.vernum >> G.arcnum;
    cout << "请输入每个节点" << endl;
    for(int i = 0;i < G.vernum;i++)
        cin >> G.data[i];
    for(int i = 0;i < G.vernum;i++)
        for(int j = 0;j < G.vernum;j++)
            G.martrix[i][j] = INITFITE;
    cout << "请输入每条边的端点及权值" <<endl;
    for(int k = 0;k < G.arcnum;k++){
        cin >> v1 >> v2 >> weight;
        int i = locate(G, v1);
        int j = locate(G,v2);
        G.martrix[i][j] = weight;
    }
}

bool visit[N];
void Dij(Graph G, char ch){
    for(int i = 0;i < N;i++)
        visit[i] = false;
    int v = locate(G,ch);
    int w;
    visit[v] = true;
    Closedge[v].pree = -1;
    int min = 1000000;
    for(int i = 0;i < G.vernum;i++){
        Closedge[i].lowcost = G.martrix[v][i];
        if(!visit[i]){
            if(Closedge[i].lowcost < INITFITE)
                Closedge[i].pree = v;
            else
                Closedge[i].pree = -1;
            if(Closedge[i].lowcost < min){
                w = i;
                min = Closedge[i].lowcost;
            }
        }
    }
    Closedge[w].pree = v;
    for(int j = 0;j < G.vernum - 1;j++){
        v = w;
        visit[v] = true;
        min = 1000000;
        for(int i = 0;i < G.vernum;i++){
            if(!visit[i]){
                if(Closedge[v].lowcost + G.martrix[v][i] < Closedge[i].lowcost){
                    Closedge[i].lowcost = Closedge[v].lowcost + G.martrix[v][i];
                    Closedge[i].pree = v;
                }
                if(Closedge[i].lowcost < min){
                    w = i;
                    min = Closedge[i].lowcost;
                }
            }
        }
    }
}

void Short_Path(Graph G, char a, char b){
    int v1 = locate(G,a);
    int v2 = locate(G,b);
    char ans[N];
    int cnt = v2;
    memset(ans,0,sizeof(ans));
    if(Closedge[v2].pree == -1 && v2 == v1){
        cout << a << "--->" << b << ":";
        cout << "This is origin " << "最短距离:" << "0" << endl;
    }
    else if(Closedge[v2].pree == -1 && v2 != v1){
        cout << a << "--->" << b << ":";
        cout << "There is no Path" << endl;
    }
    else{
        int k = 0;
        ans[k] = b;
        while(Closedge[v2].pree != v1){
            ans[++k] = G.data[Closedge[v2].pree];
            v2 = Closedge[v2].pree;
        }
        ans[++k] = a;
        cout << a << "--->" << b << ":";
        for(int i = k;i >= 0;i--)
            cout << ans[i] << " ";
        cout << "最短距离:" << Closedge[cnt].lowcost << endl;
    }

}


int main(){
    Graph G;
    Create_Graph(G);
    char c = 'x';
    for(int i = 0;i < G.vernum;i++){
        for(int j = 0;j < G.vernum;j++){
            if(G.martrix[i][j] == INITFITE)
                printf("%c\t",c);
            else
                printf("%d\t",G.martrix[i][j]);
        }
        printf("\n");
    }
    for(int i = 0;i < 5;i++){
        bool flag1 = false, flag2 = false;
        cout << "请输入要查询的两点:" << endl;
        char a, b;
        cin >> a >> b;
        for(int j = 0;j < G.vernum;j++)
        {
            if(G.data[j] == a)
                flag1 = true;
            if(G.data[j] == b)
                flag2 = true;
        }
        if(flag1 && flag2)
        {
            Dij(G,a);
            Short_Path(G,a,b);
        }
        else{
            cout << "输入地点不存在" << endl;
            continue;
        }
    }
    return 0;
}


//void Show(Graph G, char ch){
//    int v = locate(G,ch);
//    char ans[N];
//    int j, k;
//    for(int i = 0;i < G.vernum;i++){
//        memset(ans,0,sizeof(ans));
//        k = i;
//        if(Closedge[k].pree == -1 && i != v){
//            cout << ch << "---->" << G.data[i] << ":";
//            cout << "There is no way " << Closedge[i].lowcost << endl;
//        }
//        else if(Closedge[k].pree == -1 && i == v){
//            cout << ch << "---->" << G.data[i] << ":";
//            cout << "This is origin " << endl;
//        }
//        else{
//            j = 0;
//            ans[j] = G.data[k];
//            while(Closedge[k].pree != v){
//                ans[++j] = G.data[Closedge[k].pree];
//                k = Closedge[k].pree;
//            }
//            ans[++j] = G.data[v];
//            cout << ch << "---->" << G.data[i] << ":";
//            for(int q = j;q >= 0;q--){
//                cout << " " << ans[q];
//            }
//            cout << " " << Closedge[i].lowcost << endl;
//        }
//    }
//}