#include<iostream> 
using namespace std;

typedef struct
{
    int n;
    int e;
    char data[500];
    int edge[500][500];
}Graph;

typedef struct
{
    int index;
    int cost;
}mincost;

typedef struct
{
    int x;
    int y;
    int weight;
}EDGE;


typedef struct
{
    int index;
    int flag;
}F;

void create(Graph &G, int n, int e)
{
    int i, j, k, w;
    char a, b;
    for (i = 0; i < n; i++)
        cin >> G.data[i];
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            if (i == j)
                G.edge[i][j] = 0;
            else
                G.edge[i][j] = 100;
        }

    for (k = 0; k < e; k++)
    {
        cin >> a;
        cin >> b;
        cin >> w;
        for (i = 0; i < n; i++)
            if (G.data[i] == a) break;
        for (j = 0; j < n; j++)
            if (G.data[j] == b) break;

        G.edge[i][j] = w;
        G.edge[j][i] = w;
    }
    G.n = n;
    G.e = e;
}

void Prim(Graph &G, int k)
{
    int lowcost[100], closest[100];  //lowcos用来记录对应权值的节点   closet用来记录权值
    int min;

    for (int i = 0; i < G.n; i++)   //  第一次，从起点开始
    {
        closest[i] = k;
        lowcost[i] = G.edge[k][i];
    }

    int t;   //临时存储
    for (int i = 1; i < G.n; i++)
    {
        min = 100;
        for (int j = 0; j < G.n; j++)
        {
            if (lowcost[j] != 0 && lowcost[j] < min)  //寻找最小值
            {
                min = lowcost[j];
                t = j;
            }
        }

        cout << "(" << G.data[closest[t]] << "," << G.data[t] << ")";
        lowcost[t] = 0;
        for (int i = 0; i < G.n; i++)
        {
            if (G.edge[t][i] != 0 && G.edge[t][i] < lowcost[i])  //更新，将添加进来的节点与当前的节点进行比较，小的放进来，同时更新closest
            {
                lowcost[i] = G.edge[t][i];
                closest[i] = t;
            }
        }



        //完成Prim算法 

    }
}

int main()
{
    Graph my;
    int n, e;
    cin >> n >> e;
    create(my, n, e);
    Prim(my, 0);
    return 0;
}