Honest Paths

You are given a weighted undirected graph with $N$ vertices and $M$ edges. The edges are numbered from $0$ to $M − 1$, and edge $i$ connects vertices $x_i$ and $y_i$ ($x_i \neq y_i$) with weight $w_i$. There is at most one edge between any pair of vertices.

A path is a sequence of $k \geq 1$ distinct vertices $x_1, x_2, \dots , x_k$ such that there exists an edge between $x_i$ and $x_{i+1}$ for all $1 \leq i \lt k$. The length of a path is the sum of the weights of all edges along the path (equal to $0$ if the path consists of a single vertex).

It is guaranteed that there exists at least one path between any two vertices of the graph. The distance between two vertices $u$ and $v$, denoted $dist(u, v)$, is defined as the length of the shortest path connecting them.

An honest path is a path $x_1, x_2, \dots , x_k$ such that $dist(x_i, x_k) \gt dist(x_{i+1}, x_k)$ for all $1 \leq i \lt k$.

Your task is to find the longest honest path that ends at vertex $N$.

Input data

The first line contains two integers $N$ and $M$ – the number of vertices and the number of edges, respectively.

Each of the next $M$ lines contains three integers $x_i$, $y_i$ and $w_i$, describing edge $i$.

Output data

Output two lines:

• The first line should contain two integers $L$ and $K$ – the total length of the longest honest path ending at vertex $N$, and the number of vertices in that path.
• The second line should contain $K$ integers, representing the vertices of one such path in order.

If multiple solutions exist, you may output any of them.

Constraints and clarifications

• $1 \leq N \leq 500\ 000$.
• $1 \leq M \leq 500\ 000$.
• $1 \leq x_i, y_i \leq N$ for each $i = 0, 1, \dots, M − 1$.
• $1 \leq w_i \leq 1\ 000\ 000\ 000$ for each $i = 0, 1, \dots, M − 1$.
• The graph is a connected simple graph.

In this task you can get partial scores in every subtask. You will receive $50\%$ of the points for a subtask if you correctly determine the maximum length, but do not output the path itself.

If you wish to output only the length of the longest honest path, you should output $K = 0$ on the first line, and omit the second line.

Example 1

stdin

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

stdout

2 3
2 3 4

Explanation

In the first sample case an honest path ending in node $4$ is $2 → 3 → 4$. We have $dist(2, 4) = 2$,
$dist(3, 4) = 1$, $dist(4, 4) = 0$. Another honest path of maximum length is $1 → 4$.

Note that, since $dist(1, 4) = 2$, the path $1 → 2 → 3 → 4$ is not honest.

Example 2

stdin

4 4
1 2 10
2 3 1
3 4 1
1 4 3

stdout

12 4
1 2 3 4