Codeforces Round 265 (Div. 1) |
---|

Finished |

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.

data structures

graphs

shortest paths

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
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^{xi} (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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2024 17:35:03 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|