E. Minimum Path
graphs; shortest paths
You are given a weighted undirected connected graph consisting of \(n\) vertices and \(m\) edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.Let's define the weight of the path consisting of \(k\) edges with indices \(e_1, e_2, \dots, e_k\) as \(\sum\limits_{i=1}^{k}{w_{e_i}} - \max\limits_{i=1}^{k}{w_{e_i}} + \min\limits_{i=1}^{k}{w_{e_i}}\), where \(w_i\) — weight of the \(i\)-th edge in the graph.Your task is to find the minimum weight of the path from the \(1\)-st vertex to the \(i\)-th vertex for each \(i\) (\(2 \le i \le n\)).
The first line contains two integers \(n\) and \(m\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le m \le 2 \cdot 10^5\)) — the number of vertices and the number of edges in the graph.Following \(m\) lines contains three integers \(v_i, u_i, w_i\) (\(1 \le v_i, u_i \le n\); \(1 \le w_i \le 10^9\); \(v_i \neq u_i\)) — endpoints of the \(i\)-th edge and its weight respectively.
Print \(n-1\) integers — the minimum weight of the path from \(1\)-st vertex to the \(i\)-th vertex for each \(i\) (\(2 \le i \le n\)).