// yukicoder: No.92 逃走経路 // 2019.7.11 bal4u #include #include #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void out(int n) { // 正整数の表示(出力) int i; char b[20]; i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } #define INF 0x7fffffff typedef struct { int a, id; } Q; Q q[500000]; int top; typedef struct { int a, b, c; } T; T t[1005]; int M; int to[105][1005], mo[105][1005], hi[105]; int N; int d[1005], K; char ans[105], f[105][105]; int aa[2010][2], sz; int cmp(const void *a, const void *b) { return ((T *)a)->c - ((T *)b)->c; } // t[i].c >= x という条件を満たす最小のi int lower_bound(int x) { int m, l = 0, r = M; while (l+1 < r) { m = (l+r)/2; if (t[m].c < x) l = m; else r = m; } return t[l].c < x? r: l; } int dfs(int a, int id) { int i; top = 0, q[top].a = a, q[top++].id = id; while (top) { a = q[--top].a, id = q[top].id; if (id == K) return 1; for (i = 0; i < hi[a]; i++) { if (mo[a][i] == d[id]) q[top].a = to[a][i], q[top++].id = id+1; } } return 0; } int main() { int i, k, a, b, c; N = in(), M = in(), K = in(); for (i = 0; i < M; i++) { a = in(), b = in(), c = in(); t[i].a = a, t[i].b = b, t[i].c = c; k = hi[a]++, to[a][k] = b, mo[a][k] = c; k = hi[b]++, to[b][k] = a, mo[b][k] = c; } qsort(t, M, sizeof(T), cmp); t[M].c = INF; k = -1, i = K; while (i--) { d[i] = in(); if (k < 0) k = d[i]; else if (k != d[i]) k = INF; } if (k < INF && t[M-1].c == t[0].c) { k = 0; for (i = 0; i < M; i++) { a = t[i].a, b = t[i].b; if (!ans[a]) ans[a] = 1, k++; if (!ans[b]) ans[b] = 1, k++; } goto done; } i = lower_bound(d[0]); while (t[i].c == d[0]) { a = t[i].a, b = t[i].b; if (!f[a][b]) f[a][b] = 1, aa[sz][0] = t[i].a, aa[sz++][1] = t[i].b; if (!f[b][a]) f[b][a] = 1, aa[sz][0] = t[i].b, aa[sz++][1] = t[i].a; i++; } k = 0; for (i = 0; i < sz; i++) { a = aa[i][0], b = aa[i][1]; if (!ans[a] && dfs(b, 1)) ans[a] = 1, k++; } done: out(k), pc('\n'); for (i = 1; i <= N; i++) if (ans[i]) out(i), pc(' '); pc('\n'); return 0; }