最短路。。。就是在SPFA是要现算两点之间在这一时刻的dist（包括等的时间）。主要就是这个东东。。。其他就没什么了

写的时候差点要跪。。。但是竟然一次AC了~非常高兴。

听说Sgu不存代码，于是写日志吧。。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define rep(i,n) for(int i=0;i<(n);i++)
#define maxn 307
#define pb push_back
using namespace std;
const int inf=~0u>>2;
struct edge
{
	int to,c;
};

vector<edge>G[maxn];
void add(int from,int to,int c)
{
	G[from].pb((edge){to,c});
	G[to].pb((edge){from,c});
}
int d[maxn],v[maxn],pre[maxn],s,t,r[maxn],T[maxn][2];
char C[maxn][3];
queue<int>Q;
int Dist(int x,int i,int t)
{
	int y=G[x][i].to;
	bool f1=C[x][0]=='B'?0:1,f2=C[y][0]=='B'?0:1;
	int r1=r[x],r2=r[y];
	int t1=t%(T[x][0]+T[x][1]),t2=t%(T[y][0]+T[y][1]);
	if(r1>=t1)r1-=t1;
	else
	{
		r1+=T[x][f1^=1];
		if(r1>=t1)r1-=t1;
		else
		{
			r1+=T[x][f1^=1];
			r1-=t1;
		}
	}
	if(r2>=t2)r2-=t2;
	else
	{
		r2+=T[y][f2^=1];
		if(r2>=t2)r2-=t2;
		else
		{
			r2+=T[y][f2^=1];
			r2-=t2;
		}
	}
	if(r1==0)r1+=T[x][f1^=1];
	if(r2==0)r2+=T[y][f2^=1];
	if(f1==f2)return G[x][i].c;
	int c=3,tt=0;
	while(c--)
	{
		int mi=min(r1,r2);
		tt+=mi;
		r1-=mi;r2-=mi;
		if(r1==0)r1+=T[x][f1^=1];
		if(r2==0)r2+=T[y][f2^=1];
		if(f1==f2)return G[x][i].c+tt;
	}
	return inf;	
}
void spfa()
{
	memset(d,127,sizeof(d));
	memset(v,0,sizeof(v));
	Q.push(s);
	v[s]=true;
	d[s]=0;
	while(Q.size())
	{
		int x=Q.front();Q.pop();
		v[x]=false;
		rep(i,G[x].size())
		{
			edge&e=G[x][i];
			int dist=Dist(x,i,d[x]);
			if(dist==inf)continue;
			if(d[e.to]>d[x]+dist)
			{
				d[e.to]=d[x]+dist;
				pre[e.to]=x;
				if(!v[e.to])
				{
					v[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
}

vector<int>ans;	
int main()
{
	//freopen("103.in","r",stdin);
	int n,m,a,b,c;
	scanf("%d%d",&s,&t);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s%d%d%d",&C[i],&r[i],&T[i][0],&T[i][1]);
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	spfa();
	if(d[t]>=inf){printf("0\n");return 0;}
	//for(int i=1;i<n;i++)printf("%d ",d[i]);	
	printf("%d\n",d[t]);
	int u=t;
	while(u!=s)
	{
		ans.pb(u);
		u=pre[u];
	}
	ans.pb(s);
	for(int i=ans.size()-1;i>0;i--)printf("%d ",ans[i]);
	printf("%d\n",ans[0]);
	return 0;
}