// 单源最短路径和DJkstra算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<string>
using namespace std;
const int N = 20;
const int INF = 32767;
typedef struct node
{
int adj;
int weight;
struct node* nextarc;
}arcNode;
typedef struct
{
string data;
arcNode* firstArc;

}vexNode;
typedef struct
{
int n, e;
vexNode adjlist[N];
}AdjGraph;

void createGraph(AdjGraph &g)
{
cin >> g.n >> g.e;
for (int i = 0; i < g.n; i++)
{
cin >> g.adjlist .data;
g.adjlist .firstArc = NULL;
}
int u, v, w;
for (int i = 0; i < g.e; i++)
{
cin >> u >> v >> w;
arcNode* s = new arcNode;//为弧分配空间
s->adj = v;
s->weight = w;

s->nextarc = g.adjlist .firstArc;
g.adjlist .firstArc = s;
}
}
int FindMinDist(int s[],int dist[], int n)
{
int k = -1;
int minV = INF + 1;
for (int i = 0; i < n; i++)
{
if(s ==0 && dist <minV)
{
minV = dist ;
k = i;
}
}
return k;
}
void outputPath(AdjGraph& g, int v, int u, int path[])
{
if (v == u) cout << g.adjlist[v].data;
else
{
outputPath(g, v, path , path);
cout << " -> " << g.adjlist .data;
}
}

void sortDjStra(AdjGraph &g,int v)
{
int s[N] = { 0 }; //元素集合
int path[N], dist[N];

for (int i = 0; i < g.n; i++)
{
path = -1; dist = INF;
}

s[v] = 1;

arcNode* p = g.adjlist[v].firstArc;
int u;
while (p)
{
u = p->adj;
dist = p->weight;
path = v;
p = p->nextarc;
}

for (int i = 0; i < g.n-1; i++)
{
int k = FindMinDist(s, dist, g.n);
if (dist[k] == INF) break;

s[k] = 1;
arcNode* p = g.adjlist[k].firstArc;
while (p)
{
u = p->adj;
if(dist[k]+p->weight <dist )
{
dist = dist[k] + p->weight;
path = k;
}
p = p->nextarc;
}
}
//输出最短路径长度
for (int i = 0; i < g.n; i++)
{
if (i != v)
{
if (dist != INF)
{
outputPath(g, v, i, path);
cout << " :" << dist << endl;
}
}
else cout << g.adjlist[v].data << " -> " << g.adjlist .data << " :No Path"<<endl; }}int main(){ AdjGraph g; createGraph(g); sortDjStra(g, 0); return 0;}//test data/*7 12v0 v1 v2 v3 v4 v5 v60 1 40 2 60 3 61 2 11 4 72 4 62 5 43 2 23 5 54 6 65 4 15 6 8*/