我觉得这个空间（状态数）是 $O(m)$ 的啊。

#include<bits/stdc++.h>
// #pragma GCC optimize ("O2")
#define ldb long double 
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=2e5+10;
struct Edge{
    int v,col,id;
};
std::vector<Edge> p[N];
int dis[N],inf;
void add(int u,int v,int col,int id){
    p[u].push_back({v,col,id});
    p[v].push_back({u,col,id});
}
int n,m,s,t;
struct node{
    int x,dis,col,id;
};
bool vis[N];
void solve(){
    int i;
    For(i,1,n) dis[i]=inf;
    dis[s]=0;
    deque<node> q;
    q.push_back({s,0,0,0});
    while(q.size()){
        auto now=q.front();
        q.pop_front();
        if(vis[now.id]) continue;
        vis[now.id]=1;
        for(auto u:p[now.x]){
            int d=(u.col!=now.col);
            if(now.dis+d<=dis[u.v]){
                if(now.id+d==dis[u.v]&&vis[u.id]) continue;
                dis[u.v]=min(dis[u.v],now.dis+d);
                if(d)
                    q.push_back({u.v,now.dis+d,u.col,u.id});
                else
                    q.push_front({u.v,now.dis,u.col,u.id});
            }
        }
    }
    cout<<dis[t]<<'\n';
    For(i,0,m) vis[i]=0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(dis,0x3f,sizeof dis);
    inf=dis[0];
    int i,T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        For(i,1,m){
            // cout<<i<<'\n';
            int u,v,col;
            cin>>u>>v>>col;
            add(u,v,col,i);
        }
        cin>>s>>t; 
        solve();
        For(i,1,n) p[i].clear();
    }
    return 0;
}