Find The Shortest Path 4

You are given a map consisting of `n` cities and `m` bidirectional roads connecting these cities. Each road has a non-negative integer length denoted by
. Your task is to find the shortest path between city `1` and city `n`.
π‘
Note that in this task you have to find both, the length of the shortest path and the path itself.

Input

The first line contains two space-separated integers, `n` and `m` (
), representing the number of cities and the number of roads, respectively.
The next `m` lines each contain three space-separated integers
,
, and
, representing a road between cities
and
with length
(
).

Output

Two integers, `k` and `l`, separated by a space. Here, `k` represents the number of cities in the shortest path, and `l` represents the length of the shortest path.
On the next line output `k` space-separated integers representing the cities in the shortest path.
In case there are multiple shortest paths, you can output any of them. Also, note that there is no need to minimize the number `k`.

Examples

 Input Output 4 5 1 2 3 1 3 5 2 4 3 3 4 3 1 4 7 3 6 1 2 4

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 5 MB