#include using namespace std; #define M_PI 3.14159265358979323846 using ull = unsigned long long; using ll = long long; #define endl "\n" #define REP(i, n) for (ll i = 0; i < n; i++) #define REPR(i, n) for (ll i = n; i >= 0; i--) #define FOR(i, m, n) for (ll i = m; i < n; i++) #define fill(x, y) memset(x, y, sizeof(x)) #define even(x) (x) % 2 == 0 #define odd(x) (x) % 2 != 0 #define all(x) x.begin(), x.end() #define pcnt __builtin_popcount #define buli(x) __builtin_popcountll(x) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()); #define IN1(type, x) type x; cin >> x; #define inll(x) ll x; cin >> x; #define INIT() cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20) // these functions return the position of result of Binary Search. #define LB(s, t, x) (int) (lower_bound(s, t, x) - s) #define UB(s, t, x) (int) (upper_bound(s, t, x) - s) const ll MOD_CONST = (ll)(1e9 + 7); const ll CFM = (ll)(998244353); ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp ? (a / temp * b) : 0; } int mDays[] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int dx8[] = { 1, -1, 0, 0, 1, 1, -1, -1 }, dy8[] = { 0, 0, -1, 1, -1, 1, -1, 1 }; template class #if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) [[nodiscard]] #elif defined(__GNUC__) && __GNUC_PREREQ(3, 4) __attribute__((warn_unused_result)) #endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) FixPoint : F { public: explicit constexpr FixPoint(F&& f) noexcept : F(std::forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward(args)...); } }; // class FixPoint template static inline constexpr decltype(auto) makeFixPoint(F&& f) noexcept { return FixPoint{std::forward(f)}; } template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, size_t b, Ts... ts) { return vector(b, ts...))>(a, make_v(b, ts...)); } template typename enable_if::value == 0>::type fill_v(T &t, const V &v) { t = v; } template typename enable_if::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); } template vector pows(int b, int n) { // vec{b^0, b^1, b^2, ...} vector ret; T x = 1; while (ret.size() < n) { ret.push_back(x); x *= b; } return ret; } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } inline tuple rotate45(tuple point) { ll x = get<0>(point), y = get<1>(point); return tuple(x + y, x - y); } inline bool rangeCheck2D(int nx, int ny, int Width, int Height) { return nx >= 0 and nx < Width and ny >= 0 and ny < Height; } template vector INPA(ll n) { vector x; REP(i, n) { T tmp; cin >> tmp; x.push_back(tmp); } return move(x); } // base^x % MOD - O(x) ll p_base(ll base, ll x) { ll ans = 1; REP(i, x) { ans *= base; ans %= MOD_CONST; } return ans; } template void out(T o) { cout << o << endl; } template void out(vector &out) { REP(i, (int)out.size()) { cout << out[i]; if (i == (int)out.size() - 1) cout << endl; else cout << " "; } } template void out(vector> o) { REP(i, o.size()) out(o[i]); } void YesNo(bool f) { cout << (f?"Yes":"No") << endl; } void YESNO(bool f) { cout << (f?"YES":"NO") << endl; } string i_query(ll x, ll y) { cout << "? " << x << " " << y << endl; fflush(stdout); string ret; cin >> ret; return ret; } void i_answer(ll ans) { cout << "! " << ans << endl; fflush(stdout); } // use " for (const auto& e : V) // lambda expression // auto f = [](int arg1, double arg2) { return ret; }; // lambda recursion // auto result = makeFixPoint([&](auto rec, int pos, int v) -> int { // rec(pos, v); // })(0, 1); // auto func = makeFixPoint([]() -> int {}); // int ret = func(); // tuple binding // auto t = make_tuple(0, 0); // int x, y; tie(x, y) = t; // auto [x, y] = t; // for pair // auto [a, b] = pair({v1, v2}); // bitset bs(ini_val); // N must be constant // bs.reset(); // reset all class ListG { public: // there's directed edge between A and B // if to[A] has element B vector> to; map, ll> cost; void setCost(int u, int v, ll c) { cost[{min(u, v), max(u, v)}] = c; } ll getCost(int u, int v) { return cost[{min(u, v), max(u, v)}]; } ListG(int s) : root(-1) { size = s; to = make_v>(size); } void setDirectedEdge(int f, int t) { to[f].push_back(t); } void setIndirectedEdge(int v1, int v2) { setDirectedEdge(v1, v2); setDirectedEdge(v2, v1); } void dfs(vector &visiting, vector &visited, int current, vector> &cloop) { for (auto&& next : to[current]) { if (visited[next]) continue; if (visiting[next]) { cloop[current].push_back(next); visited[next] = 1; dfs(visiting, visited, next, cloop); visited[next] = 0; } else { visiting[next] = 1; dfs(visiting, visited, next, cloop); visiting[next] = 0; } } } // return max depth int makeTree(int r) { root = r; p = make_v(size); p[root] = -1; depth = make_v(size); int maxDepth = 0; makeFixPoint([&](auto rec, int c, int d) -> void { depth[c] = d; chmax(maxDepth, d); REP(i, to[c].size()) { int next = to[c][i]; if (p[c] == next) continue; p[next] = c; rec(next, d + 1); } })(root, 0); // count leaf node auto idxs = make_v(size); iota(all(idxs), 0); leaf_idx = set(all(idxs)); REP(i, size) { if (i == root) continue; leaf_idx.erase(p[i]); } return maxDepth; } void makeEulerTour() { assert(root >= 0); et_begin = make_v(size); et_end = make_v(size); tmp_k = 0; etdfs(root, -1); } vector> children() { assert(root >= 0); auto ret = make_v>(size); REP(i, size) { int prt = p[i]; if (prt == -1) continue; ret[prt].push_back(i); } return ret; } int stronglyConnectedConponent() { auto rto = make_v>(size); REP(from, size) { for (auto&& t : to[from]) rto[t].push_back(from); } auto cmp = make_v(size); fill_v(cmp, 0); auto used = make_v(size); fill_v(used, 0); vector rets; // return index in order REP(i, size) { makeFixPoint([&](auto dfs, int v) -> void { if (used[v]) return; used[v] = 1; for (auto&& t : to[v]) dfs(t); rets.push_back(v); })(i); } fill_v(used, 0); int ret = 0; REPR(i, rets.size()-1) { makeFixPoint([&](auto rdfs, int v, int k) -> void { if (used[v]) return; used[v] = 1; cmp[v] = k; for (auto&& rt : rto[v]) rdfs(rt, k); rets.push_back(v); })(rets[i], ret++); } return ret; } vector topologicalSorted() { vector ret; auto used = make_v(size); fill_v(used, 0); REP(i, size) { makeFixPoint([&](auto dfs, int v) -> void { if (used[v]) return; used[v] = 1; for (auto&& t : to[v]) dfs(t); ret.push_back(v); })(i); } reverse(all(ret)); return ret; } void dfsTree(ListG& dfst) { auto visited = make_v(size); auto prt = make_v(size); fill_v(visited, 0); fill_v(prt, 0); stack st; st.push(0); while (st.size()) { int c = st.top(); st.pop(); if (visited[c]) continue; visited[c] = 1; if (c != 0) dfst.setIndirectedEdge(c, prt[c]); for (const auto& next : to[c]) { prt[next] = c; st.push(next); } } } int size, root; vector p; // parent for each node. parent of root = -1 vector depth; // for each node. depth of root node = 0 vector euler_tour; vector et_begin, et_end; set leaf_idx; int tmp_k; private: void etdfs(int vidx, int pidx) { et_begin[vidx] = tmp_k; euler_tour.push_back(vidx); tmp_k++; REP(i, to[vidx].size()) { if (to[vidx][i] != pidx) { etdfs(to[vidx][i], vidx); euler_tour.push_back(vidx); tmp_k++; } } et_end[vidx] = tmp_k; } }; int main(void) { INIT(); // comment out for Interective Program inll(N); inll(M); inll(K); auto a = make_v(M); auto b = make_v(M); auto c = make_v(M); ListG lg(N+1); REP(i, M) { cin >> a[i] >> b[i] >> c[i]; lg.setIndirectedEdge(a[i], b[i]); lg.setCost(a[i], b[i], c[i]); } auto d = INPA(K); set> cand; // from to REP(i, M) { if (c[i] == d[0]) { cand.insert({a[i], b[i]}); cand.insert({b[i], a[i]}); } } set> ncand; FOR(i, 1, K) { for (const auto& [from, to] : cand) { for (const auto& next : lg.to[to]) { if (lg.getCost(to, next) != d[i]) continue; ncand.insert({to, next}); } int nto = from; for (const auto& next : lg.to[nto]) { if (lg.getCost(nto, next) != d[i]) continue; ncand.insert({to, next}); } } cand = ncand; ncand = set>(); } auto candd = vector>(all(cand)); auto ans = make_v(cand.size()); REP(i, cand.size()) ans[i] = candd[i].second; UNIQUE(ans); out(ans.size()); sort(all(ans)); out(ans); return 0; }