You are given a weighted undirected graph on n vertices and m edges. Find the shortest path from vertex s to vertex t or else state that such path doesn't exist.

Input

The first line of the input contains two space-separated integers — n and m (1 ≤ n ≤ 105; 0 ≤ m ≤ 105).

Next m lines contain the description of the graph edges. The i-th line contains three space-separated integers — ui, vi, xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 105). That means that vertices with numbers ui and vi are connected by edge of length 2xi (2 to the power of xi).

The last line contains two space-separated integers — the numbers of vertices s and t.

The vertices are numbered from 1 to n. The graph contains no multiple edges and self-loops.

Output

In the first line print the remainder after dividing the length of the shortest path by 1000000007 (109 + 7) if the path exists, and -1 if the path doesn't exist.

If the path exists print in the second line integer k — the number of vertices in the shortest path from vertex s to vertex t; in the third line print k space-separated integers — the vertices of the shortest path in the visiting order. The first vertex should be vertex s, the last vertex should be vertex t. If there are multiple shortest paths, print any of them.

Examples

Input

4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4


Output

3
4
1 2 3 4 


Input

4 3
1 2 4
2 3 5
3 4 6
1 4


Output

112
4
1 2 3 4 


Input

4 2
1 2 0
3 4 1
1 4


Output

-1

Note

A path from vertex s to vertex t is a sequence v0, ..., vk, such that v0 = s, vk = t, and for any i from 0 to k - 1 vertices vi and vi + 1 are connected by an edge. 

The length of the path is the sum of weights of edges between vi and vi + 1 for all i from 0 to k - 1. 

The shortest path from s to t is the path which length is minimum among all possible paths from s to t.
#include <bits/stdc++.h>
using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
template <class T>
inline bool cmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
inline int read() {
  char ch;
  bool flag = 0;
  int res;
  while (!isdigit(
      ch = (p1 == p2 &&
                    (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
                ? EOF
                : *p1++)))
    (ch == '-') && (flag = true);
  for (res = ch - '0'; isdigit(
           ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin),
                             p1 == p2)
                     ? EOF
                     : *p1++));
       res = res * 10 + ch - '0')
    ;
  (flag) && (res = -res);
  return res;
}
const int N = 1e5 + 5, mod = 1e9 + 7;
int n, m, head[N], Next[N << 1], ver[N << 1], edge[N << 1];
int S, T, lim, b[N << 1], rt[N], Pre[N], tot, cnt;
int L[N * 120], R[N * 120], sum[N * 120];
inline void add(int u, int v, int e) {
  ver[++tot] = v, Next[tot] = head[u], head[u] = tot, edge[tot] = e;
  ver[++tot] = u, Next[tot] = head[v], head[v] = tot, edge[tot] = e;
}
bool cmp(int u, int v, int l, int r) {
  if (l == r) return sum[u] > sum[v];
  int mid = (l + r) >> 1;
  if (sum[R[u]] == sum[R[v]])
    return cmp(L[u], L[v], l, mid);
  else
    return cmp(R[u], R[v], mid + 1, r);
}
int update(int last, int &now, int l, int r, int k) {
  L[now = ++cnt] = L[last], R[now] = R[last];
  if (l == r) {
    sum[now] = sum[last] ^ 1;
    return sum[last];
  }
  int mid = (l + r) >> 1, res;
  if (k > mid)
    res = update(R[last], R[now], mid + 1, r, k);
  else {
    res = update(L[last], L[now], l, mid, k);
    if (res) res = update(R[last], R[now], mid + 1, r, k);
  }
  sum[now] = (1ll * sum[R[now]] * b[mid - l + 1] + sum[L[now]]) % mod;
  return res;
}
struct node {
  int x, rt;
  bool operator<(const node &b) const { return cmp(rt, b.rt, 0, lim); }
};
priority_queue<node> q;
void dfs(int u, int dep) {
  if (u == S) {
    printf("%d\n%d ", dep, u);
    return;
  }
  dfs(Pre[u], dep + 1);
  printf("%d ", u);
}
void print(int u) {
  printf("%d\n", sum[rt[u]]);
  dfs(u, 1);
  exit(0);
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    int u, v, e;
    u = read(), v = read(), e = read();
    add(u, v, e);
    cmax(lim, e);
  }
  lim += 18;
  b[0] = 1;
  for (int i = 1; i <= lim; ++i) b[i] = (1ll * b[i - 1] << 1) % mod;
  S = read(), T = read();
  q.push((node){S, rt[S]});
  while (!q.empty()) {
    node u = q.top();
    q.pop();
    if (u.rt != rt[u.x]) continue;
    if (u.x == T) print(T);
    for (int i = head[u.x]; i; i = Next[i]) {
      int v = ver[i], RT;
      update(u.rt, RT, 0, lim, edge[i]);
      if (!rt[v] || cmp(rt[v], RT, 0, lim))
        rt[v] = RT, q.push((node){v, rt[v]}), Pre[v] = u.x;
    }
  }
  puts("-1");
  return 0;
}
