这是原题

我的代码，就超时了一个点

#include<bits/stdc++.h>
using namespace std;
const int maxn = 52,maxs = 1e5+10; 
long long dis[maxn][maxs];
bool vis[maxn];
long long n,m,x,d;
vector<int> g[maxn];
int W[maxn][maxn];
void spfa(){
	queue<int> que;
	que.push(1);
	dis[1][0] = 0;
	vis[1] = 1;
	while(!que.empty()){
		int u = que.front();
		que.pop();
		vis[u] = 0;
		for(int v:g[u]){
			
			int w = W[u][v];
			for(int p = 0;p < 2*d;p++){
			if(dis[u][p] == x+1)continue;
			//cout<<u<<" "<<p<<endl;
			 
			if(dis[v][(dis[u][p]+w)%(2*d)] > dis[u][p]+w){
				dis[v][(dis[u][p]+w)%(2*d)] = dis[u][p]+w;
				if(!vis[v]){
					vis[v] = 1;
					que.push(v);
				}
			}
		    }
		}
	}
}
int main(){
	//freopen("rolling.in","r",stdin);
	//freopen("rolling.out","w",stdout);
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>x;
		for(int i = 1;i <= m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back(v);
			g[v].push_back(u);
			W[u][v] = w;
			W[v][u] = w;
		}
		for(int i = 0;i < maxn;i++){
			for(int j = 0;j < maxs;j++){
				dis[i][j] = x+1;
			}
			vis[i] = 0;
		}
		d = W[1][g[1][0]];
		spfa();
		//cout<<dis[n][x%(2*d)]<<endl;
		if(dis[n][x%(2*d)] <= x){
			cout<<"possible"<<endl;
		}
		else{
			cout<<"impossible"<<endl;
		}
		for(int i = 1;i <= n;i++){
			g[i].clear();
		}
	}
}