CF1473E Minimum Path

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 $ ).