rt，主席树+dij

WA on #13

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define N 200005
#define LL long long
#define MOD 1000000007

using namespace std;
int n,m,S,T; LL mul[N];

int cnt,head[N];
struct Node { int to,nxt,dis; }e[N];

void add(int u,int v,int w) { e[++cnt]=Node{v,head[u],w},head[u]=cnt; }

int tcnt,rt[N];
struct Tree { LL sum; int len,ls,rs; }t[N<<6];

void upd(int &x,int y,int l,int r,int pos) {
    t[x=++tcnt]=t[y];
    if (l==r) return t[x].sum+=mul[l],t[x].len++,void();
    int mid=(l+r>>1);
    if (pos<=mid) upd(t[x].ls,t[y].ls,l,mid,pos);
    else upd(t[x].rs,t[y].rs,mid+1,r,pos);
    t[x].sum=(t[t[x].ls].sum+t[t[x].rs].sum)%MOD;
    t[x].len=t[t[x].ls].len+t[t[x].rs].len;
}

bool cmp(int x,int y,int l,int r) {
    if (!x) return 0;
    if (!y) return 1;
    if (l==r) return t[x].len>t[y].len;
    int mid=(l+r>>1);
    if (t[t[x].rs].sum==t[t[y].rs].sum and t[t[x].rs].len==t[t[y].rs].len)
        return cmp(t[x].ls,t[y].ls,l,mid);
    else return cmp(t[x].rs,t[y].rs,mid+1,r);
}

struct Q {
    int u,rt;

    bool operator<(const Q tmp) const { return cmp(rt,tmp.rt,0,N-1); }
};

LL dis[N]; bool vis[N]; int to[N];
priority_queue<Q> q;

void dij() {
    memset(dis,-1,sizeof dis);
    memset(vis,0,sizeof vis);
    q.push({S,rt[S]=++tcnt}); dis[S]=0;
    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].to,w=e[i].dis,tmp;
            upd(tmp,rt[u],0,N-1,w);
            if (Q{0,rt[v]}<Q{0,tmp} or dis[v]==-1) {
                // printf("u: (%d, %lld) v: (%d, %lld)\n",u,t[tmp].sum,v,dis[v]);
                dis[v]=t[tmp].sum,rt[v]=tmp,to[v]=u;
                q.push({v,rt[v]});
            }
        }
    }
}

void dfs(int u) {
    if (!u) return;
    dfs(to[u]);
    printf("%d ",u);
}

int main() {
    scanf("%d%d",&n,&m);
    mul[0]=1; for (int i=1;i<N;i++) mul[i]=mul[i-1]*2%MOD;
    for (int i=1,u,v,w;i<=m;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w); add(v,u,w);
    }
    scanf("%d%d",&S,&T);
    dij();
    if (dis[T]==-1) printf("-1\n");
    else {
        printf("%lld\n%d\n",dis[T],t[rt[T]].len+1);
        dfs(T); printf("\n");
    }
    return 0;
}