Shortest path - MarisaOJ: Marisa Online Judge

Given an undirected, weighted graph of

$n$ vertices and

$m$ edges. Find the shortest path from

$1$ to

$n$ . ### Input - The first line contains 2 integers

$n, m$ . - The next

$m$ lines, each line contains 3 integers

$u, v, w$ , there is an edge of weight

$w$ connecting

$u, v$ . ### Output - Print the weight of the shortest path on one line, then print the path on another line. Print

$-1$ if no solution exists. In case there are more than 1 solution, print any. ### Constraints -

$1 \le n, m \le 2 \times 10^5$ . -

$1 \le u, v \le n$ . -

$1 \le w \le 10^9$ . ### Example Input:

$3 3 1 2 1 2 3 2 1 3 3$

Output:

$3 1 2 3$

Topic

Graph

Shortest path

Rating

1000

Solution (0)

Solution