Statement

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 ≠ y_i) with weight w_i. There is at most one edge between any pair of vertices. A path is a sequence of k ≥ 1 distinct vertices x_1, x_2, …, x_k such that there exists an edge between x_i and x_i+1 for all 1 ≤ i < 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, …, x_k such that dist(x_i, x_k) > dist(x_i+1, x_k) for all 1 ≤ i < k. Your task is to find the longest honest path that ends at vertex N.