思路与第一篇题解一致。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mn=114514,mod=1e9+7;
vector<int> l[mn],w[mn],ansq;
int n,m,s,t,u,v,ww;
int maxw,f[mn];
ll n2[mn];
ll ans;

int root[mn],proot,lroot;
int tot,pp,pl,pr;

bool isin[mn],iss[mn];

struct tree{
	int l,r,mid;
	ll hash;
	bool is1;
}tre[128*mn];

void edge(int u,int v,int ww){
	l[u].push_back(v);
	l[v].push_back(u);
	w[u].push_back(ww);
	w[v].push_back(ww);
	return;
}

bool isbig(int p1,int p2,int s,int e){
	if(s>=e){
		if(tre[p1].is1) return true;
		return false;
	}
	
	if(tre[tre[p1].r].hash==tre[tre[p2].r].hash) return isbig(tre[p1].l,tre[p2].l,s,tre[p1].mid);
	return isbig(tre[p1].r,tre[p2].r,tre[p1].mid+1,e);
}

struct cmp{
	bool operator()(int a,int b){
		return isbig(root[a],root[b],0,maxw);
	}
};

void build(int p,int s,int e){
	if(s>=e) return;
	
	tre[p].mid=(s+e)/2;
	tre[p].l=++tot;
	build(tre[p].l,s,tre[p].mid);
	tre[p].r=++tot;
	build(tre[p].r,tre[p].mid+1,e);
	
	return;
}

int find(int p,int s,int e){
	if(tre[p].is1) return e;
	else if(s>=e) return pp-1;
	
	int pans=pp-1;
	if(pp<=tre[p].mid){
		pans=find(tre[p].l,s,tre[p].mid);
		if(pans>=tre[p].mid) pans=max(pans,find(tre[p].r,tre[p].mid+1,e));
	}
	else if(pp<=e) pans=max(pans,find(tre[p].r,tre[p].mid+1,e));
	
	return pans;
}

void emp(int p,int yp,int sp,int s,int e){
	tre[p].mid=tre[yp].mid;
	
	if(pl<=s && pr>=tre[p].mid) tre[p].l=tre[sp].l;
	else if(pl<=tre[p].mid && pr>=s){
		tre[p].l=++tot;
		emp(tre[p].l,tre[yp].l,tre[sp].l,s,tre[p].mid);
	}
	else tre[p].l=tre[yp].l;
	
	if(pl<=tre[p].mid+1 && pr>=e) tre[p].r=tre[sp].r;
	else if(pl<=e && pr>tre[p].mid){
		tre[p].r=++tot;
		emp(tre[p].r,tre[yp].r,tre[sp].r,tre[p].mid+1,e);
	}
	else tre[p].r=tre[yp].r;
	
	tre[p].hash=(tre[tre[p].l].hash+tre[tre[p].r].hash*n2[tre[p].mid-s+1])%mod;
	
	return;
}

void mdf(int p,int yp,int s,int e){
	if(s>=e){
		tre[p].is1=tre[p].hash=1;
		return;
	}
	
	tre[p].mid=tre[yp].mid;
	if(pp<=tre[p].mid){
		tre[p].l=++tot,tre[p].r=tre[yp].r;
		mdf(tre[p].l,tre[yp].l,s,tre[p].mid);
	}
	else{
		tre[p].l=tre[yp].l,tre[p].r=++tot;
		mdf(tre[p].r,tre[yp].r,tre[p].mid+1,e);
	}
	
	tre[p].is1=(tre[tre[p].l].is1 && tre[tre[p].r].is1);
	tre[p].hash=(tre[tre[p].l].hash+tre[tre[p].r].hash*n2[tre[p].mid-s+1])%mod;
	
	return;
}

void add(int pw){
	pp=pw;
	pl=pw,pr=find(proot,0,maxw);
	if(pr>=pl){
		lroot=proot;
		proot=++tot;
		emp(proot,lroot,1,0,maxw);
	}
	pp=pr+1;
	lroot=proot;
	proot=++tot;
	mdf(proot,lroot,0,maxw);
	return;
}

priority_queue<int,vector<int>,cmp> q;

void dijkstra(){
	
	tot=root[s]=1;
	build(1,0,maxw);
	
	int p=0;
	q.push(s);
	
	while(!q.empty()){
		p=q.top();
		q.pop();
		if(isin[p]) continue;
		if(p==t) break;
		isin[p]=true;
		for(int i=0;i<l[p].size();i++) if(!isin[l[p][i]]){
			
			proot=++tot;
			tre[proot]=tre[root[p]];
			add(w[p][i]);
			
			if(!iss[l[p][i]]){
				iss[l[p][i]]=true;
				root[l[p][i]]=++tot;
				tre[root[l[p][i]]]=tre[proot];
				q.push(l[p][i]);
				f[l[p][i]]=p;
			}
			else if(isbig(root[l[p][i]],proot,0,maxw)){
				tre[root[l[p][i]]]=tre[proot];
				q.push(l[p][i]);
				f[l[p][i]]=p;
			} 
		}
	}
	
	return;
}

int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d%d",&u,&v,&ww);
		maxw=max(maxw,ww);
		edge(u,v,ww);
	}
	scanf("%d%d",&s,&t);
	maxw+=20; 
	
	if(s==t){
		cout<<0<<endl<<2<<endl<<s<<' '<<t<<endl;
		return 0;
	}
	
	n2[0]=1;
	for(int i=1;i<=maxw;i++) n2[i]=n2[i-1]*2%mod;
	
	dijkstra();
	
	if(!root[t]) cout<<-1<<endl;
	else{
		ans=tre[root[t]].hash;
		int pt=t;
		ansq.push_back(t);
		while(pt!=s){
			pt=f[pt];
			ansq.push_back(pt);
		}
		
		cout<<ans<<endl<<ansq.size()<<endl;
		for(int i=ansq.size()-1;i>=0;i--) cout<<ansq[i]<<' ';
		cout<<endl;
	}
	
	return 0;
}