Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. The Classic Problem

time limit per test

5 secondsmemory limit per test

768 megabytesinput

standard inputoutput

standard outputYou 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* ≤ 10^{5}; 0 ≤ *m* ≤ 10^{5}).

Next *m* lines contain the description of the graph edges. The *i*-th line contains three space-separated integers — *u* _{ i}, *v* _{ i}, *x* _{ i} (1 ≤ *u* _{ i}, *v* _{ i} ≤ *n*; 0 ≤ *x* _{ i} ≤ 10^{5}). That means that vertices with numbers *u* _{ i} and *v* _{ i} are connected by edge of length 2^{ x i} (2 to the power of *x* _{ i}).

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 (10^{9} + 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 *v* _{0}, ..., *v* _{ k}, such that *v* _{0} = *s*, *v* _{ k} = *t*, and for any *i* from 0 to *k* - 1 vertices *v* _{ i} and *v* _{ i + 1} are connected by an edge.

The length of the path is the sum of weights of edges between *v* _{ i} and *v* _{ i + 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*.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2020 05:56:43 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|