虚点 + bfs

#include <bits/stdc++.h>
#define re register int 
using namespace std;
const int N = 4e5 + 10, M = 2e5 + 10;

struct edge
{
	int x, y, c;
}e[M];
int dep[N], color[N], idx;
int T, n, m, s, t;
vector<int> g[N], path;

inline void build()
{
	for (re i = 1; i <= m; i ++)
	{
		int x = e[i].x, y = e[i].y, c = e[i].c;
		if (!color[c]) color[c] = ++ idx;
		g[n + color[c]].push_back(x);
		g[n + color[c]].push_back(y);
		g[x].push_back(n + color[c]);
		g[y].push_back(n + color[c]);
	}
}

inline void bfs()
{
	queue<int> q;
	
	q.push(s);
	dep[s] = 1;
	
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		
		for (re i = 0; i < g[x].size(); i ++)
		{
			int y = g[x][i];
			
			if (!dep[y])
			{
				dep[y] = dep[x] + 1;
				q.push(y);
			}
		}
	}
}

inline void print()
{
	int u = t;
	path.push_back(u);
	
	while (u != s)
	{
		for (re i = 0; i < g[u].size(); i ++)
		{
			int v = g[u][i];
			
			if (dep[v] + 1 == dep[u])
			{
				path.push_back(v);
				u = v;
			}
		}
	}
	cout << path.size() / 2 << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> T;
	
	while (T --)
	{
		memset(e, 0, sizeof(e));
		memset(dep, 0, sizeof(dep));
		memset(color, 0, sizeof(color));
		idx = 0;
		path.clear();
		
		cin >> n >> m;
		for (re i = 1; i <= m; i ++)
			cin >> e[i].x >> e[i].y >> e[i].c;
		cin >> s >> t;
		
		build();
		bfs();
		print();
		
		for (re i = 1; i <= n + m + 1; i ++) g[i].clear();	
	}
	
	return 0;
}