高橋君が移動する様子を考えます。高橋君が頂点 \(a\) の次に頂点 \(b\) に出現した時、

• 自身が \(ab\) 辺を通過して \(a\) から \(b\) へ移動するか、
• 頂点 \(a\) で分裂して、タカとハシがともに頂点 \(b\) に移動してそこで合体する

という 2 通りのいずれかであることがわかります。よって補助グラフ \(G_1\) を

• 高橋君が通れる辺の両端、および
• 以下の条件を満たす頂点の組 \((a,b)\)
  • タカとハシが共に、頂点 \(a\) を出発して合体することなく自身が通れる辺を経由して頂点 \(b\) に到達できる。

の間に辺を貼ったグラフとした時、\(G_1\) 上で頂点 \(1\) と連結な頂点が答えとなります。
よって \(G_1\) と連結性において等価なグラフを構成すれば答えを求められます。これは補助グラフ \(G_2, G_3\) をそれぞれラベル \(2\) の辺、ラベル \(3\) の辺のみからなるグラフとした時、\(G_2, G_3\) に対応する Union-Find \(U_2, U_3\) を構成して (U_2.leader(i), U_3.leader(i)) に注目することで計算できます。
計算量は \(\mathrm{O}((N+M) \alpha(N))\) 程度で十分高速です。

• 実装例(C++)

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;

#include "atcoder/dsu.hpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;
    atcoder::dsu uf1(N), uf2(N), uf3(N);
    for (int i = 0; i < M; i++) {
      int u, v, l;
      cin >> u >> v >> l;
      --u, --v;
      (l == 1 ? uf1 : l == 2 ? uf2 : uf3).merge(u, v);
    }

    map<pair<int, int>, int> mp;
    for (int i = 0; i < N; i++) {
      auto p = make_pair(uf2.leader(i), uf3.leader(i));
      if (mp.count(p)) uf1.merge(mp[p], i);
      mp[p] = i;
    }

    vector<int> ans;
    for (int i = 0; i < N; i++) {
      if (uf1.same(0, i)) ans.push_back(i + 1);
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); i++) {
      cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
    }
  }
}