基本上就是 AcWing 1029. NOI2017 整数 一题的扩展，只不过不压 30 位，每一位直接表示成二进制应该也能过。然后在此基础上需要多版本，还要判断高精度大小。高精度数大小就按照字符串 Hash 的思想二分查找 LCP 即可。多版本就直接用可持久化线段树来维护即可。然后每次加法进位的时候不要用永久化来做，而是直接无脑都赋值为 0 就行了。

const int N = 100010, V = 4000, LOG_V = 13;
const int key = 1 << 30, mask = key - 1;
const int mod_1 = 1000000007, mod_2 = 1045430273;
// part 1 : hash

int p1[V], p2[V];
struct table_initializer
{
    table_initializer()
    {
        p1[0] = p2[0] = 1;
        for (int i = 1; i < V; ++i)
            p1[i] = 1ll * p1[i - 1] * key % mod_1, p2[i] = 1ll * p2[i - 1] * key % mod_2;
    }
} t_init;
// part 2 : persistent seg-tree
namespace seg
{
    struct node
    {
        int lc, rc;
        int sz; // sz = R - L + 1
        int and_sum;
        int hc1, hc2; // hashcode
    } tr[4 * N * (LOG_V + 1)];
    int rt[4 * N + 2], cnt;
    inline int new_node(int v) { return tr[++cnt] = tr[v], cnt; }
    inline void adjust_hash(int u) { tr[u].hc1 = tr[u].and_sum - ((tr[u].and_sum >= mod_1) ? mod_1 : 0), tr[u].hc2 = tr[u].and_sum - ((tr[u].and_sum >= mod_2) ? mod_2 : 0); }
    inline void pushup(int u)
    {
        tr[u].and_sum = tr[tr[u].lc].and_sum & tr[tr[u].rc].and_sum;
        tr[u].hc1 = ((1ll * tr[tr[u].rc].hc1 * p1[tr[tr[u].lc].sz] % mod_1) + tr[tr[u].lc].hc1) % mod_1;
        tr[u].hc2 = ((1ll * tr[tr[u].rc].hc2 * p2[tr[tr[u].lc].sz] % mod_2) + tr[tr[u].lc].hc2) % mod_2;
    }
    inline int _build(int l, int r, bool flag) // build 0 : all zero 1 : all one
    {
        int u = ++cnt;
        tr[u].sz = r - l + 1;
        if (l == r) return tr[u].and_sum = flag ? mask : 0, adjust_hash(u), u;
        int m = (l + r) >> 1;
        tr[u].lc = _build(l, m, flag), tr[u].rc = _build(m + 1, r, flag);
        return pushup(u), u;
    }
    inline void build() { rt[0] = _build(0, V, 0), rt[1] = _build(0, V, 1); }
    inline int _query_single(int u, int pos, int L, int R)
    {
        if (L == R)
            return tr[u].and_sum;
        int M = (L + R) >> 1;
        return (pos <= M) ? _query_single(tr[u].lc, pos, L, M) : _query_single(tr[u].rc, pos, M + 1, R);
    }
    inline int query_single(int cur, int pos) { return _query_single(rt[cur], pos, 0, V); }
    inline int _add_single(int v, int pos, int L, int R, int val)
    {
        int u = new_node(v);
        if (L == R)
            return tr[u].and_sum += val, adjust_hash(u), u;
        int M = (L + R) >> 1;
        (pos <= M) ? (tr[u].lc = _add_single(tr[v].lc, pos, L, M, val)) : (tr[u].rc = _add_single(tr[v].rc, pos, M + 1, R, val));
        return pushup(u), u;
    }
    inline void add_single(int cur, int pre, int pos, int val) { rt[cur] = _add_single(rt[pre], pos, 0, V, val); }
    inline int _find_right_mask(int u, int pos, int L, int R)
    {
        if (tr[u].and_sum == mask)
            return R;
        else if (L == R)
            return -1;
        int M = (L + R) >> 1, ret = -1;
        if (pos <= M)
        {
            ret = _find_right_mask(tr[u].lc, pos, L, M);
            if (ret == M) ret = std::max(ret, _find_right_mask(tr[u].rc, pos, M + 1, R));
        }
        else ret = _find_right_mask(tr[u].rc, pos, M + 1, R);
        return ret;
    }
    inline int find_right_mask(int cur, int pos) { return _find_right_mask(rt[cur], pos, 0, V); }
    inline int _modify_zero(int v, int no, int l, int r, int L, int R)
    {
        if (l > R || r < L)
            return v;
        if (l <= L && R <= r)
            return no;
        int M = (L + R) >> 1, u = new_node(v);
        tr[u].lc = _modify_zero(tr[v].lc, tr[no].lc, l, r, L, M);
        tr[u].rc = _modify_zero(tr[v].rc, tr[no].rc, l, r, M + 1, R);
        return pushup(u), u;
    }
    inline void modify_zero(int cur, int pre, int l, int r) { rt[cur] = _modify_zero(rt[pre], rt[0], l, r, 0, V); }
    // judge by hash LCP -1(<) 1(>) 0(==)
    inline int _compare(int u, int v, int L, int R)
    {
        if (L == R)
            return (tr[u].and_sum < tr[v].and_sum) ? -1 : (tr[u].and_sum > tr[v].and_sum) ? 1 : 0;
        int M = (L + R) >> 1;
        return ((tr[tr[u].rc].hc1 == tr[tr[v].rc].hc1) && (tr[tr[u].rc].hc2 == tr[tr[v].rc].hc2)) ? _compare(tr[u].lc, tr[v].lc, L, M) : _compare(tr[u].rc, tr[v].rc, M + 1, R);
    }
    inline int compare(int fi, int se) { return _compare(rt[fi], rt[se], 0, V); }
    // pre + 2^b = cur
    inline void real_add(int cur, int pre, int b)
    {
        int pos = b / 30, val = 1 << (b % 30);
        int val_pre = query_single(pre, pos);
        if (val_pre + val <= mask)
            add_single(cur, pre, pos, val);
        else
        {
            add_single(cur, pre, pos, val - key);
            int q = find_right_mask(cur, pos);
            (q != -1) ? (modify_zero(cur, cur, pos + 1, q), add_single(cur, cur, q + 1, 1)) : (add_single(cur, cur, pos + 1, 1));
        }
    }
}
int n, m, s, t;
int u, v, w;
// part 3 graph
namespace graph
{
    int to[N << 1], w[N << 1], nxt[N << 1], h[N], cnt;
    void add_edge(int u, int v, int _w) { to[++cnt] = v, w[cnt] = _w, nxt[cnt] = h[u], h[u] = cnt; }
    void link(int u, int v, int _w) { add_edge(u, v, _w), add_edge(v, u, _w); }
}
// part 4 dijkstra
struct node
{
    int id, v;
    node(int i = 0, int _v = 0) : id(i), v(_v) {}
    bool operator<(const node& o) const { return seg::compare(o.v, v) < 0; }
};
std::priority_queue<node> pq;
int ver_cnt;
int dis_ver[N];
int path[N];
int route[N], route_sz;
bool vis[N];
void dijkstra(int S, int T)
{
    seg::build(), ver_cnt = 1;
    std::fill(dis_ver + 1, dis_ver + n + 1, 1), dis_ver[S] = 0;
    pq.push(node(S, 0));
    while (!pq.empty())
    {
        node tmp = pq.top();
        pq.pop();
        int u = tmp.id, dis_u = tmp.v;
        if (vis[u]) continue;
        if (u == T) break;
        vis[u] = 1;
        for (int i = graph::h[u]; i; i = graph::nxt[i])
        {
            int v = graph::to[i], w = graph::w[i];

            if (!vis[v])
            {
                seg::real_add(++ver_cnt, dis_u, w);
                if (seg::compare(ver_cnt, dis_ver[v]) < 0)
                    dis_ver[v] = ver_cnt, path[v] = u, pq.push(node(v, ver_cnt));
            }
        }
    }
}
int main()
{
    n = rd(), m = rd();
    while (m--) u = rd(), v = rd(), w = rd(), graph::link(u, v, w);
    s = rd(), t = rd();
    dijkstra(s, t);
    if (seg::compare(dis_ver[t], 1) >= 0) puts("-1");
    else
    {
        wr(seg::tr[seg::rt[dis_ver[t]]].hc1), putchar('\n');
        while (path[t] != t) route[++route_sz] = t, t = path[t];
        wr(route_sz), putchar('\n');
        for (int i = route_sz; i; --i) wr(route[i]), putchar(' ');
    }
}