记录编号	345067	评测结果	AAAAAAAAAA
题目名称	通向聚会的套路	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.993 s
提交时间	2016-11-10 19:16:11	内存使用	2.38 MiB

// 建反图, 从n点求出到各个点的最短距离
// 注意原来的odd变成了even

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

const int maxnumber = 10010, inf = 0x3f3f3f3f;
int n, m;
struct Edge
{
	int to, w, next;
	int odd, even;
	inline Edge(): odd(0), even(0) {}
}edges[maxnumber * 10];
string house[maxnumber];
int head[maxnumber], tot;
int dis[maxnumber][2];// dis[i][0]: 走过奇数个点到达i的最短距离
struct Node
{
	int pos, tot, type;// type: 已经走过的点的个数的奇偶
	inline Node(const int& a, const int& b, const int& c): pos(a), tot(b), type(c) {}
	inline bool operator < (const Node& a) const { return tot > a.tot; }
};
priority_queue <Node> Q;

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

inline void Dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[n][1] = dis[n][0] = 0;
	Q.push(Node(n, 0, 0)); Q.push(Node(n, 0, 1));
	while (!Q.empty()) {
		Node top = Q.top(); Q.pop();
		int pos = top.pos, tot = top.tot, type = top.type;
		if (tot != dis[pos][type]) continue;
		for (int i = head[pos]; i; i = edges[i].next) {
			int to = edges[i].to, w = edges[i].w, odd = edges[i].odd, even = edges[i].even;
			if (!type && odd)
				if (dis[to][type ^ 1] > dis[pos][type] + w) {
					dis[to][type ^ 1] = dis[pos][type] + w;
					Q.push(Node(to, dis[to][type ^ 1], type ^ 1));
				}
			if (type && even)
				if (dis[to][type ^ 1] > dis[pos][type] + w) {
					dis[to][type ^ 1] = dis[pos][type] + w;
					Q.push(Node(to, dis[to][type ^ 1], type ^ 1));
				}
			if (!even && !odd)
				if (dis[to][type ^ 1] > dis[pos][type] + w) {
					dis[to][type ^ 1] = dis[pos][type] + w;
					Q.push(Node(to, dis[to][type ^ 1], type ^ 1));
				}
		}
	}
	// for (int i = 1; i <= n; ++i)
	// 	printf("dis[%d]:%d %d\n", i, dis[i][0], dis[i][1]);
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("party_ezoi.in", "r", stdin); freopen("party_ezoi.out", "w", stdout);
#endif

	int from, to, w, p, num;
	int ans = inf;
	string ch;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &from, &to, &w);
		AddEdge(to, from, w);
	}
	scanf("%d", &p);
	while (p--) { scanf("%d", &num); edges[num].even = 1; }// 奇偶相反
	scanf("%d", &p);
	while (p--) { scanf("%d", &num); edges[num].odd = 1; }
	scanf("%d", &p);
	while (p--) { scanf("%d", &num); cin >> house[num]; }

	Dijkstra();

	for (int i = 1; i <= n; ++i)
		if (!house[i].empty()) ans = min(ans, dis[i][1]);
	for (int i = 1; i <= n; ++i) {
		if (dis[i][1] == ans && !house[i].empty()) {
			if (ch.empty()) ch = house[i];
			else ch = min(ch, house[i]);
		}
	}
	cout << ch << endl;
	printf("%d\n", ans);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}