分析
显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。
因为边权全部是 $2$ 的幂，因此考虑拿线段树维护每个二进制位。这样子加法就只要二分出一段 $1$ 并将其赋值为 $0$，再在高位填上一个 $1$，比较大小可以在线段树上二分出 LCP 然后比较低位。因此我们需要在线段树上维护区间和和区间哈希值（直接自然溢出啥事没有.jpg）。这样子比较大小是 $\mathcal{O}(\log n)$ 的，加法是 $\mathcal{O}(\log^2 n)$ 的，因此总复杂度 $\mathcal{O}(n\log^2 n)$。
因为每个节点的 $dis$ 都是一棵线段树，而我们又不能直接在原来的线段树上修改，所以需要可持久化线段树。
因为若干个 $2^{10^6}$ 加起来显然是大于 $2^{10^6}$ 的，所以数组要略微开大一点。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100200+10,L=100200;
const int BASE=19491001;
const int mod=1e9+7;
int n,m,S,T;
struct edge { int v,w,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v,int w) {
static int cnt=0;
e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
ull pw[N]; int pw2[N];
#define ls(o) t[o].ls
#define rs(o) t[o].rs
int rt[N],tot=0;
struct node { int sum,val,ls,rs; ull hash; } t[N*150];
void pushup(int o) {
t[o].sum=t[ls(o)].sum+t[rs(o)].sum;
t[o].val=(t[ls(o)].val+t[rs(o)].val)%mod;
t[o].hash=t[ls(o)].hash+t[rs(o)].hash;
}
void build(int& o,int l,int r) {
if (!o) o=++tot;
if (l==r) return;
int mid=(l+r)>>1;
build(ls(o),l,mid),build(rs(o),mid+1,r);
pushup(o);
}
void modify(int& o,int l,int r,int p) {
t[++tot]=t[o],o=tot;
if (l==r) {
t[o].sum=1,t[o].val=pw2[l],t[o].hash=pw[l];
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(ls(o),l,mid,p);
else modify(rs(o),mid+1,r,p);
pushup(o);
}
bool cmp(int x,int y,int l,int r) {
if (l==r) return t[x].sum>t[y].sum;
int mid=(l+r)>>1;
if (t[rs(x)].hash==t[rs(y)].hash) return cmp(ls(x),ls(y),l,mid);
else return cmp(rs(x),rs(y),mid+1,r);
}
void assign(int& o,int z,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) { o=z; return; }
t[++tot]=t[o],o=tot;
int mid=(l+r)>>1;
if (ql<=mid) assign(ls(o),ls(z),l,mid,ql,qr);
if (qr>mid) assign(rs(o),rs(z),mid+1,r,ql,qr);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o].sum;
int mid=(l+r)>>1,res=0;
if (ql<=mid) res+=query(ls(o),l,mid,ql,qr);
if (qr>mid) res+=query(rs(o),mid+1,r,ql,qr);
return res;
}
#undef ls
#undef rs
void add(int& o,int p) {
if (!query(o,0,L,p,p)) { modify(o,0,L,p); return; }
int l=p,r=L;
while (l<r) {
int mid=(l+r+1)>>1;
if (query(o,0,L,p,mid)==mid-p+1) l=mid;
else r=mid-1;
}
assign(o,rt[0],0,L,p,l),modify(o,0,L,l+1);
}
struct Hnode { int u,d; };
bool operator <(Hnode a,Hnode b) { return cmp(a.d,b.d,0,L); }
priority_queue<Hnode> Q;
int vis[N],lst[N];
void dijkstra() {
build(rt[0],0,L),rt[S]=rt[0]; Q.push((Hnode){S,rt[S]});
while (!Q.empty()) {
int u=Q.top().u; Q.pop();
if (vis[u]) continue; vis[u]=1;
for (int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (vis[v]) continue;
int t=rt[u]; add(t,w);
if (!lst[v]||cmp(rt[v],t,0,L))
lst[v]=u,rt[v]=t,Q.push((Hnode){v,rt[v]});
}
}
}
vector<int> ans;
int main() {
n=read(),m=read();
for (int i=1;i<=m;++i) {
int u=read(),v=read(),w=read();
addEdge(u,v,w),addEdge(v,u,w);
}
pw[0]=pw2[0]=1;
for (int i=1;i<=L;++i) pw[i]=pw[i-1]*BASE;
for (int i=1;i<=L;++i) pw2[i]=2ll*pw2[i-1]%mod;
S=read(),T=read();
dijkstra();
if (!vis[T]) { puts("-1"); return 0; }
printf("%d\n",t[rt[T]].val);
for (int i=T;i;i=lst[i]) ans.emplace_back(i);
reverse(ans.begin(),ans.end());
printf("%lu\n",ans.size());
for (int i:ans) printf("%d ",i); puts("");
return 0;
}