Minimum Sum Path in a Weighted Graph

Given an undirected connected weighted graph with n vertices and m edges, your task is to find a path from vertex 1 to vertex n such that the sum of the edge weights is minimized.

The graph is described by m edges. Each edge is represented by three integers u, v, and w, which indicate that there is an edge between vertices u and v with weight w.

If the required path is represented by a sequence of vertices: 1, a₂, a₃, ..., a_k = n, then the total weight of the path is given by:

$\sum_{i=1}^{k-1} w(a_i, a_{i+1})$

Your goal is to minimize this sum.

inputFormat

The first line contains two integers n and m, where n is the number of vertices and m is the number of edges.

Each of the following m lines contains three integers u, v, and w, representing an undirected edge between vertices u and v with weight w.

outputFormat

The output consists of two lines. The first line should contain the minimum total weight of the path from vertex 1 to vertex n. The second line should list the vertices along the path (from 1 to n) separated by spaces.

## sample

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

2
1 4 5

</p>