void dfs(vector<int>& signal,vector<bool> & mask, vector<vector<int> > &path, vector<vector<int> >& matrix, int nowNode, int T,int nowTime, int & minValue){

 if(nowTime >= minValue) return;

 if(nowNode == T){

 minValue = min(minValue, nowTime);

 return;

 }

 int waitTime = 0;

 if(nowTime / signal[nowNode] % 2 == 1) {

 waitTime = signal[nowNode] - nowTime % signal[nowNode];

 }

 nowTime += waitTime;

 mask[nowNode] = true;

 for(int i=0;i<path[nowNode].size();i++){

 if(!mask[path[nowNode][i]]){

 nowTime += matrix[nowNode][path[nowNode][i]];

 dfs(signal,mask,path,matrix,path[nowNode][i],T,nowTime,minValue);

 nowTime -= matrix[nowNode][path[nowNode][i]];

 }

 }

 mask[nowNode] = false;

}

int minTravelTime(int N, vector < vector < int > > intersections, int M, vector < vector < int > > roads, int s, int t) {

 vector<bool> mask(N,false);

 vector<int> signal(N,0);

 for(int i=0;i<N;i++){

 signal[intersections[i][0]] = intersections[i][1];

 }

 vector<vector<int> > path(N);

 vector<vector<int> > matrix(N,vector<int>(N,0));

 for(int i=0;i<M;i++){

 path[roads[i][0]].push_back(roads[i][1]);

 path[roads[i][1]].push_back(roads[i][0]);

 matrix[roads[i][0]][roads[i][1]] = roads[i][2];

 matrix[roads[i][1]][roads[i][0]] = roads[i][2];

 }

 int result = 0x7fffffff;

 dfs(signal,mask,path,matrix,s,t,0,result);

 return result;

}