不想写主席树所以写了分块。思路和主席树类似，考虑将每个数的二进制分块，每一次加法最多新增两个块，暴力维护。

对拍拍不出来，且换过哈希方式仍然 wa，感觉可能是逻辑上写挂了，但是看不出来。

代码：

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,m,s,t;
vector<pair<int,int>> e[100010];
int block=350;
int tot=2; int dis[200010][360]; int hsh[200010];
vector<int> wz[100010];
bool cmp(vector<int> wz1,vector<int> wz2)
{
	for(int i=block-1; i>=0; --i)
	{
		if(hsh[wz1[i]]!=hsh[wz2[i]])
		{
			for(int j=block; j>=1; --j)
			{
				if(dis[wz1[i]][j]!=dis[wz2[i]][j]) return dis[wz1[i]][j]<dis[wz2[i]][j];
			}
		}
	}
	return 1;
}
vector<int> add(int x,int w)
{
	vector<int> now;
	for(int i=0; i<=block-1; ++i)
	{
		if((i+1)*block-1<w) now.push_back(wz[x][i]);
		else
		{
			bool flag=1;
			int ed;
			for(int j=w-i*block+1; j<=block; ++j)
			{
				if(dis[wz[x][i]][j]==0) { flag=0,ed=j; break; }
			}
			if(flag)
			{
				++tot;
				memcpy(dis[tot],dis[wz[x][i]],sizeof(dis[wz[x][i]]));
				for(int j=w-i*block+1; j<=block; ++j) dis[tot][j]=0;
				for(int j=1; j<=block; ++j) hsh[tot]=(hsh[tot]*2+dis[tot][j])%mod;
				now.push_back(tot);
				int wwz=i+1;
				while(hsh[wwz]==hsh[2]) now.push_back(1),++wwz;
				for(int j=1; j<=block; ++j)
				{
					if(dis[wz[x][wwz]][j]==0) { ed=j; break; }
				}
				++tot;
				memcpy(dis[tot],dis[wz[x][wwz]],sizeof(dis[wz[x][wwz]]));
				for(int j=1; j<ed; ++j) dis[tot][j]=0;
				dis[tot][ed]=1;
				for(int j=1; j<=block; ++j) hsh[tot]=(hsh[tot]*2+dis[tot][j])%mod;
				now.push_back(tot);
				for(int j=wwz+1; j<=block-1; ++j) now.push_back(wz[x][j]);
			}
			else
			{
				++tot;
				memcpy(dis[tot],dis[wz[x][i]],sizeof(dis[wz[x][i]]));
				for(int j=w-i*block+1; j<ed; ++j) dis[tot][j]=0;
				dis[tot][ed]=1;
				for(int j=1; j<=block; ++j) hsh[tot]=(hsh[tot]*2+dis[tot][j])%mod;
				now.push_back(tot);
				for(int j=i+1; j<=block-1; ++j) now.push_back(wz[x][j]);
			}
			return now;
		}
	}
}
struct Prio
{
	int now; vector<int> wz;
	bool operator < (Prio x) const
	{
		return cmp(x.wz,wz);
	}
}; priority_queue<Prio> q;
bool vis[100010];
int pre[100010];
int main()
{
	cin>>n>>m;
	for(int i=1; i<=m; ++i)
	{
		int u,v,w; cin>>u>>v>>w;
		e[u].push_back({v,w}),e[v].push_back({u,w});
	}
	cin>>s>>t;
	for(int i=1; i<=block; ++i) hsh[2]=(hsh[2]*2+1)%mod;
	for(int i=1; i<=block; ++i) dis[2][i]=1;
	for(int i=1; i<=n; ++i)
	{
		for(int j=1; j<=block; ++j) wz[i].push_back(i==s?1:2);
	}
	q.push({s,wz[s]});
	while(!q.empty())
	{
		int frn=q.top().now; q.pop();
		if(vis[frn]) continue; vis[frn]=1;
		for(pair<int,int> vv:e[frn])
		{
			int v=vv.first,w=vv.second;
			if(vis[v]) continue;
			vector<int> gt=add(frn,w);
			if(cmp(gt,wz[v])) wz[v]=gt,q.push({v,wz[v]}),pre[v]=frn;
		}
	}
	if(!vis[t]) return cout<<-1,0;
	int ans=0,pow2=1;
	for(int i=0; i<=block-1; ++i)
	{
		for(int j=1; j<=block; ++j) ans=(ans+dis[wz[t][i]][j]*pow2)%mod,pow2=pow2*2%mod;
	}
	cout<<ans<<'\n';
	stack<int> st;
	while(t!=s) st.push(t),t=pre[t];
	st.push(s);
	cout<<st.size()<<'\n';
	while(!st.empty()) cout<<st.top()<<' ',st.pop();
	return 0;
}